이분탐색?

이분탐색(Binary Search)은 모든 수를 탐색하는 방식과 달리,
이미 정렬되어있는 배열에서 절반씩 범위를 좁혀나가며 타겟을 찾는 알고리즘이다.

const sample = [10, 5, 3, 1, 2, 6, 8, 9, 4];
sample.sort((a, b) => a - b);

function binarySearch(list, target, left, right) {
  let mid = 0;

  while (left <= right) {
    mid = Math.floor((left + right) / 2);

    if (list[mid] === target) {
      return mid;
    }

    if (list[mid] > target) {
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
  return -1;
}

var answer = binarySearch(sample, 9, 0, sample.length - 1);
console.log(answer);

left,right,mid 세 변수를 이용하는 특징이 있다.
left는 왼쪽 끝 인덱스, right는 오른쪽 끝, mid는 left+right/2 중앙값이다.
탐색하는 범위를 절반씩 버려가며 줄여나가기에, 시간복잡도는 O(logN) 이다.