이진 탐색(Binary-Search)

정렬된 형태의 자료구조에서 특정 값을 찾기 위해서는 이진 탐색을 이용할 수 있다.

처음 요소부터 마지막 요소까지 순차적으로 탐색하는 선형 방식의 시간 복잡도는 $O(N)$ 이지만, 이진 탐색을 이용하면 $O(logN)$ 만에 탐색을 끝낼 수 있다.

특히 입력 데이터가 큰 경우일수록 유용하다.

특정 값 찾기

배열에서 특정한 값 target의 인덱스 위치를 찾는 이분 탐색 알고리즘은 다음과 같다.

현재 탐색하려는 중간 값 mid를 (start + end) / 2로 한다.
만약 target이 현재 값보다 작다면 왼쪽 부분을 가지고 이분 탐색 해야한다. 따라서 end를 mid - 1로 설정한다.
만약 target이 현재 값보다 크다면 오른쪽 부분을 가지고 이분 탐색 해야한다. 따라서 start를 mid + 1로 설정한다.
만약 target이 현재 값과 같다면 현재 인덱스인 mid를 반환한다.
이분 탐색이 끝날 때까지 같은 값을 찾지 못했다면 null을 반환한다.

function binarySearch(arr, start, end, target) {
  while (start < end) {
    const mid = Math.floor((start + end) / 2);
    const value = arr[mid];

    if (target < value)
      end = mid - 1;
    else if (target > value)
      start = mid + 1;
    else return mid;
  }

  return null;
}

LowerBound

배열에서 특정한 값이 중복해서 존재할 수도 있을 때, 특정한 값 target이 나타나기 시작하는 가장 첫 번째 위치를 반환하거나, 혹은 동일한 값이 없다면 그 바로 다음 인덱스를 반환하는 알고리즘이다.

현재 탐색하려는 중간 값 mid를 (start + end) / 2로 한다.

만약 target이 현재 값보다 크다면 오른쪽 부분을 가지고 이분 탐색 해야한다. 따라서 start를 mid + 1로 설정한다.

만약 target이 현재 값보다 작거나 같다면 왼쪽 부분을 가지고 이분 탐색 해야한다. 따라서 end를 mid로 설정한다.

이분 탐색이 끝나면 start나 end 둘 중 하나를 아무거나 반환한다.

function lowerBound(arr, start, end, target) {
  while (start < end) {
    const mid = Math.floor((start + end) / 2);
    const value = arr[mid];

    if (target > value) start = mid + 1;
    else end = mid;
  }

  return start;
}

UpperBound

배열에서 특정한 값이 중복해서 존재할 수도 있을 때, 특정한 값 target 보다 큰 요소가 나타나는 가장 첫 번째 위치를 반환하는 알고리즘이다.

현재 탐색하려는 중간 값 mid를 (start + end) / 2로 한다.

만약 target이 현재 값보다 크거나 같다면 오른쪽 부분을 가지고 이분 탐색 해야한다. 따라서 start를 mid + 1로 설정한다.

만약 target이 현재 값보다 작다면 왼쪽 부분을 가지고 이분 탐색 해야한다. 따라서 end를 mid로 설정한다.

이분 탐색이 끝나면 start나 end 둘 중 하나를 아무거나 반환한다.

function upperBound(arr, start, end, target) {
  while (start < end) {
    const mid = Math.floor((start + end) / 2);
    const value = arr[mid];

    if (target >= value) start = mid + 1;
    else end = mid;
  }

  return start;
}

활용 사례

LowerBound나 UpperBound는 값이 반드시 일치하지 않아도 가장 근사한 인덱스를 반환 하므로 예를 들어 다음과 같은 경우에 유용하게 사용할 수 있다.

정렬된 배열에 데이터를 삽입할 때 적합한 위치를 찾음.
배열에 특정 요소가 몇 개 존재하는지 구함.

실행 예시

const datas = [0, 10, 20, 30, 30, 50, 60, 70, 80, 90];
console.log(lowerBound(datas, 0, datas.length, 30));
console.log(upperBound(datas, 0, datas.length, 30));

3
5