이진 검색 알고리즘

정의

이진 검색은 검색 간격을 반으로 반복해서 나누어 정렬된 배열에서 사용되는 검색 알고리즘입니다. 이진 검색의 아이디어는 배열이 정렬된 정보를 사용하고 시간 복잡도를 O(Log n)으로 줄이는 것입니다.

비교

시간 복잡도가 O(n)인 선형 검색에 비해 이진 검색 Big O 표기법은 O(log n)입니다.

이진 검색은 선형 검색보다 훨씬 빠르게 정렬된 배열을 검색할 수 있습니다.

실생활 예

1부터 50까지 숫자를 생각하고 있어 정답은 1

선형 검색

숫자 = 50 ? 아니
번호 = 49 ? 아니
...
숫자 = 2 ? 아니
숫자 = 1 ? 예!

최악의 경우 50번의 추측이 필요합니다!

이진 검색

숫자 = 25 ? 아니오, 덜
숫자 = 12 ? 아니오, 덜
숫자 = 6 ? 아니오, 덜
숫자 = 3 ? 아니오, 덜
숫자 = 2 ? 아니오, 덜
숫자 = 1 ? 예!

최악의 경우 6번의 추측이 필요합니다!

결론

1,000,000개의 숫자를 가정합니다!
선형 검색은 1,000,000개의 추측(최악의 경우)을 초래합니다.
이진 검색은 20개의 추측(최악의 경우)을 초래합니다.

심상

이진 검색

선형 검색

코딩

const binarySearch = (sortedArr, value) => {
  let left = 0;
  let right = sortedArr.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    const midVal = sortedArr[mid];

    if (midVal === value) {
      return mid;
    } else if (midVal < value) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return -1;
};