이진 탐색

이진 탐색(Binary Search)은 정렬된 배열에서 원하는 값을 빠르게 찾는 알고리즘입니다. 시간 복잡도는 O(log n)으로 매우 효율적입니다.

---

1. 이진 탐색 개념

• 배열이 정렬되어 있어야만 사용할 수 있음
• 중간 값을 기준으로 절반씩 버리면서 탐색
• 목표 값이 중간보다 작으면 왼쪽 범위로, 크면 오른쪽 범위로 이동

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

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

    if (arr[mid] === target) return mid;
    if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }

  return -1; // 찾지 못했을 경우
}

2. 응용

배열에 같은 값이 여러 개 있을 때, 그중에서도 특정 위치(가장 왼쪽 또는 가장 오른쪽) 값을 찾고 싶을 때 사용하는 이진 탐색 응용입니다.

가장 왼쪽 인덱스 찾기

function lowerBound(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  let result = -1;

  while (left <= right) {
    let mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) {
      result = mid;
      right = mid - 1; // 왼쪽으로 더 찾아보기
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return result;
}

가장 오른쪽 인덱스 찾기

function upperBound(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  let result = -1;

  while (left <= right) {
    let mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) {
      result = mid;
      left = mid + 1; // 오른쪽으로 더 찾아보기
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return result;
}

Lower Bound : target이상의 같이 최초로 나오는 위치.

/**
 * lowerBound: 정렬된 배열에서 target 이상의 값이
 * 처음 나타나는 인덱스를 반환한다.
 * (C++ std::lower_bound와 동일한 동작)
 *
 * @param {number[]} arr   오름차순으로 정렬된 배열
 * @param {number}   target 찾고자 하는 기준 값
 * @returns {number}  조건을 만족하는 최소 인덱스
 *                    └ 없으면 arr.length (삽입 위치)
 */
function lowerBound(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  let minIdx = arr.length;          // 기본값: 배열 뒤 (없을 때 삽입 위치)

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

    if (arr[mid] >= target) {       // target 이상이면 후보
      minIdx = Math.min(minIdx, mid);
      right = mid - 1;              // 더 왼쪽에 있을지 탐색
    } else {
      left = mid + 1;               // target보다 작으므로 오른쪽으로
    }
  }

  return minIdx;
}

/* 사용 예시 */
const nums = [2, 4, 4, 6, 8, 10];
console.log(lowerBound(nums, 5)); // 3  (값 6이 있는 위치)
console.log(lowerBound(nums, 4)); // 1  (첫 번째 4)
console.log(lowerBound(nums, 11)); // 6 (배열 길이 → 삽입 위치)

Upper Bound : target을 초과하는 값이 최초로 나오는 위치

/**
 * upperBound: 정렬된 배열에서 target 초과 값이
 * 처음 나타나는 인덱스를 반환한다.
 * (C++ std::upper_bound와 동일한 동작)
 *
 * @param {number[]} arr    오름차순 정렬된 배열
 * @param {number}   target 초과 기준 값
 * @returns {number} 조건을 만족하는 최소 인덱스 (없으면 arr.length)
 */
function upperBound(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  let minIdx = arr.length;

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

    if (arr[mid] > target) {
      minIdx = Math.min(minIdx, mid); // 후보 저장
      right = mid - 1;                // 더 왼쪽도 탐색
    } else {
      left = mid + 1;                 // target 이하 → 오른쪽 탐색
    }
  }

  return minIdx;
}

target보다 같거나 작은 숫자들의 위치중 가장 큰 위치

function customBound(arr, target){
  let left = 0;
  let right = arr.length;
  let mid_index = -1

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

    if(arr[mid] <= target){
      left = mid+1;
      mid_index = Math.max(mid_index, mid)
    }else{
      right = mid - 1
    }
  }
  return mid_index
}