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

[dididy]

개념

정렬된 데이터가 있을 때 특정 값을 효율적으로 찾을 수 있는 알고리즘이다. 가운데 값을 기준으로 오른쪽, 왼쪽 각각의 값보다 큰지 작은지를 파악하여 해당 범위의 중앙값을 선택하여 반복하는 과정을 수행하면 원하는 값을 찾을 수 있다.

구현

function binarySearch(target, array) {
  let start = 0;
  let end = array.length - 1;
  while (start <= end) {
    let mid = Math.floor((end + start) / 2);
    const guess = array[mid];

    if (guess === target) {
      return guess;
    }

    if (guess > target) {
      end = mid - 1;
      continue;
    }

    start = mid + 1;
  }

  return undefined;
}

시간복잡도

O(logN)

[dididy]

https://www.acmicpc.net/problem/2343