이진 탐색과 그 응용

이진 탐색을 하기 위한 전제조건으로, 요소들이 먼저 정렬이 되어있어야 한다.

특정 숫자 찾기

const list = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
const target = 9;

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

    while(left <= right) {
        const midIdx = Math.floor((left + right) / 2);
        if (list[midIdx] === target) return true;
        if (list[midIdx] < target) {
            left = midIdx + 1;
        } else {
            right = midIdx - 1;
        }
    }
    return false;
}

lower bound

lower bound는 찾고자 하는 값 이상이 처음 나타나는 위치

// target 이상이 처음 나타나는 위치를 찾아라
// 만약 모든 요소가 target 보다 클 경우 n + 1 을 리턴한다. 
const list = [0, 1, 2, 5, 5, 5, 5, 7, 8, 9];
const target = 5; 
// 원하는 결과: 3

// lower bound: >= target
function lowerBound(list, target) {
    // 모든 원소가 target보다 작을때에는 n + 1 을 출력해야하므로 처음 구간을 잡을때 [0, n] 을 잡는다.
  let left = 0;
  let right = list.length; 

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

        // list[m] >= target 이면서 list[m-1] < target 를 만족하는 최소 m을 찾는 문제
        if (list[m] >= target) {            
            right = m
        } else {
            left = m + 1;
        }
  }

  return left;
}

upper bound

upper bound는 찾고자 하는 값보다 큰 값이 처음으로 나타나는 위치

// target을 초과하는 숫자가 처음 나타나는 위치를 찾아라
// 만약 모든 요소가 target 보다 작을 경우 n + 1 을 리턴한다. 
const list = [0, 1, 2, 5, 5, 5, 5, 7, 8, 9];
const target = 5;
// 원하는 결과: 7

// upper bound: > target
function upperBound(list, target) {
    // 모든 원소가 target보다 작을때에는 n + 1 을 출력해야하므로 처음 구간을 잡을때 [0, n] 을 잡는다.
  let left = 0;
  let right = list.length;

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

        // list[m] > target 이면서 list[m-1] <= target 을 만족하는 최소 m을 찾는 문제
    if (list[m] > target) {
      right = m;
    } else {
      left = m + 1;
    }
  }

  return left;
}