이진 탐색 알고리즘 (Binary Search Algorithm)

지은·2022년 11월 17일

Algorithm

목록 보기

6/33

이진 탐색 알고리즘 (Binary Search Algorithm)

: 오름차순으로 정렬된 숫자 배열에서 검색 범위를 1 / 2씩 줄여가며 원하는 데이터를 검색하는 알고리즘

정렬된 배열과 찾고자하는 데이터를 입력하면, 해당 데이터의 index를 리턴한다.
배열에 찾고자하는 데이터가 존재하지 않으면 -1 을 리턴한다.

입출력 예

arr	target	return
[-5, 2, 4, 6, 10]	6	3
[-5, 2, 4, 6, 10]	99	-1

의사 코드

function binarySearch (arr, target) {
  let 맨 왼쪽 인덱스 =0
  let 맨 오른쪽 인덱스 = arr.length - 1;
  
  반복문 (맨 왼쪽 인덱스와 맨 오른쪽 인덱스가 같아질 때까지 반복문을 돌린다.) {
    let 둘의 가운데 인덱스 = 맨 왼쪽 인덱스 + 맨 오른쪽 인덱스 / 2;
    
    만약 (타겟 = 가운데 인덱스라면) {
      가운데 인덱스를 리턴한다.
    }
    
    만약 (타겟이 가운데 인덱스보다 작다면) { 👉 맨 왼쪽 ~ 가운데 사이에 타겟이 있다는 뜻이므로
      맨 오른쪽 인덱스를 가운데 인덱스 - 1 로 갱신한다.
    }
    
    만약 (타겟이 가운데 인덱스보다 크다면) { 👉 가운데 ~ 맨 오른쪽 사이에 타겟이 있다는 뜻이므로
      맨 왼쪽 인덱스를 가운데 인덱스 + 1 로 갱신한다. 
    }
  }
  반복문이 종료되었는데도 값을 찾지 못했다면, 없다는 뜻이므로 -1을 리턴한다.
}

풀이

function binarySearch (arr, target) {
  let leftIndex = 0;
  let rightIndex = arr.length - 1;
  
  while (leftIndex <= rightIndex) {
    let midIndex = Math.floor((leftIndex + rightIndex) / 2);
    
    if (target === arr[midIndex]) {
      return midIndex;
    } else if (target < arr[midIndex]) {
      rightIndex = midIndex - 1;
    } else {
      leftIndex = midIndex + 1;
    }
  }
  return -1;
}

재귀를 이용한 풀이

의사 코드

function recursiveBinarySearch (arr, target, leftIndex, rightIndex) {
  // base case
  만약 (배열이 빈 배열이라면) {
    타겟을 찾을 수 없으므로 -1 을 리턴한다.
  }
  // recursive case
  그렇지 않다면
  let midIndex = 가운데 인덱스
  
  만약 (타겟이 중간 요소와 같다면) {
    중간 요소의 인덱스를 리턴한다.
  } 만약 (타겟이 중간 요소보다 작다면) {
    배열의 왼쪽 절반을 recursiveBinarySearch 한다.
  } 만약 (타겟이 중간 요소보다 크다면) {
    배열의 오른쪽 절반을 recursiveBinarySearch 한다.
  }

}

풀이

function recursiveBinarySearch (arr, target, leftIndex, rightIndex) {
  // base case
  if (leftIndex > rightIndex) {
    return - 1;
  }
  // recursive case
  let midIndex = Math.floor((leftIndex + rightIndex) / 2);
  if (target === arr[midIndex]){
    return midIndex;
  } else if (target < arr[midIndex]) {
    return recursiveBinarySearch(arr, target, leftIndex, midIndex - 1);
  } else {
    return recursiveBinarySearch(arr, target, midIndex + 1, rightIndex);
  }
}