이진 탐색(Binary Search) 알고리즘 개념 이해 및 예제 feat. Javascript

이진탐색(Binary Search)?

이진 탐색이란 *정렬된* 배열에서 특정한 값을 찾아내는 알고리즘입니다. 배열의 중간 값과 찾고자 하는 값을 비교하며 찾아냅니다. 찾고자 하는 값이 X라고 하면, X가 중간 값보다 작으면(x<mid) 중간 값을 기준으로 좌측의 데이터들을 대상으로, X가 중간값보다 크면(mid<x) 배열의 우측의 데이터들을 대상으로 다시 탐색합니다. 해당 과정을 찾고자 하는 값을 찾을 때까지 반복합니다. 아래 이미지는 이진탐색 동작 과정에 대한 시각화 예시입니다.

이진탐색(Binary Search) 예시

매 순회 검색을 완료할 때마다 검색하려는 데이터가 반절씩 줄어들기 때문에 순차적으로 찾는 방식보다 훨씬 효율적입니다. 매 순회마다 탐색 범위가 절반씩 줄어들기 때문에 시간복잡도는 O(logN)입니다.

빅오표기법 시간복잡도 예시

코드 구현 예시

자바스크립트로 이진탐색을 구현한 예시입니다. 재귀함수로 구현했기 때문에, 탈출조건을 신경써서 작성하셔야 합니다. 탈출조건을 제대로 작성하지 않으면, 무한루프에 빠질 수 있습니다.

// 랜덤값으로 구성된 정렬된 배열 생성
function makeRandomArr() {
  const arr = [];
  for (let i = 0; i < 10000000; i++) {
    arr.push(Math.floor(Math.random() * 10000000));
  }

  return arr.sort((a, b) => a - b);
}

// bst
// 재귀함수 예시
function bSearch(arr, target, low, high) {
  if (low > high) return -1;
  const mid = Math.floor((low + high) / 2);
  // console.log('search...', low, mid, high)
  if (arr[mid] === target) return mid;

  if (arr[mid] > target) {
    return bSearch(arr, target, low, mid - 1);
  } else {
    return bSearch(arr, target, mid + 1, high);
  }
}
const arr = makeRandomArr();
bSearch(arr, 547835, 0, arr.length - 1);

해당 이진탐색 코드를 실행하면, 아래의 과정으로 원하는 값을 찾아내는 것을 확인할 수 있습니다.

search... 0 4999999 9999999
search... 0 2499999 4999998
search... 0 1249999 2499998
search... 0 624999 1249998
search... 0 312499 624998
search... 312500 468749 624998
search... 468750 546874 624998
search... 546875 585936 624998
search... 546875 566405 585935
search... 546875 556639 566404
search... 546875 551756 556638
search... 546875 549315 551755
search... 546875 548094 549314
search... 548095 548704 549314
search... 548095 548399 548703
search... 548095 548246 548398
search... 548247 548322 548398
search... 548247 548284 548321
search... 548247 548265 548283
search... 548247 548255 548264
search... 548247 548250 548254
search... 548251 548252 548254
search... 548253 548253 548254

548253