이진 검색(바이너리 서치)

이진 검색이란?

검색할 데이터 열이 정렬되어 있다면, 이진 검색으로 원하는 데이터를 빠르게 찾을 수 있다.

시간 복잡도 O(logn)

N: 데이터 개수, T: 찾고자 하는 값, M: 중앙 위치

1 단계: 중앙 위치 M을 N/2로 만든다.
2 단계: 검색 범위 안의 데이터 개수가 1개 이상이라면 다음 3단계를 반복한다.
3 단계: 
	T = DATA[M]일 때: 데이터를 찾았으므로 반복 중단
	T < DATA[M]일 때: DATA[M] 및 DATA[M]의 오른쪽(큰 값)에 데이터 T는 절대 
    			     존재하지 않으므로, 검색 범위를 위치 M보다 왼쪽(작은 값)으로 좁힌다.
    T > DATA[M]일 때: DATA[M] 및 DATA[M]의 왼쪽(작은 값)에 데이터 T는 절대 
    				 존재하지 않으므로, 검색 범위를 위치 M보다 오른쪽(큰 값)으로 좁힌다.

예시 문제

function solution(target, arr) {
  let answer;
  arr.sort((a, b) => a - b);
  let lt = 0;
  let rt = arr.length - 1;

  while (lt <= rt) {
    let mid = parseInt((lt + rt) / 2, 10);
    if (arr[mid] === target) {
      answer = mid + 1;
      break;
    } else if (arr[mid] > target) rt = mid - 1;
    else lt = mid + 1;
  }
  return answer;
}

let arr = [23, 87, 65, 12, 57, 32, 99, 81];
console.log(solution(32, arr));