[알고리즘] 이분탐색

이분탐색

• 이분 탐색(Binary Search)은 정렬된 데이터에서 특정 값을 빠르게 찾는 대표적인 탐색 알고리즘이다.
• 전체 구간을 반으로 나누어가며, 목표값을 찾을 때마다 검색 범위를 반씩 줄여가는 방식이다.
• 시간복잡도는 O(log n)으로 매우 효율적.

이분 탐색의 동작 원리

• 데이터가 정렬되어 있을 때 중간값과 목표값을 비교.
• 목표값이 중간값보다 작으면 왼쪽 구간으로, 크면 오른쪽 구간으로 탐색을 이동
• 반복적으로 구간을 반으로 좁히며, 값이 발견되거나 구간이 소진될 때까지 수행

이분 탐색 예시

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid  # 타겟값의 인덱스 반환
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1  # 찾지 못할 경우 -1

function binarySearch(arr, target) {
  let left = 0, 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; // 값 없음
}

파이썬에는 이분 탐색을 위해 bisect 모듈이 존재한다.

• bisect_left(arr, x)

  • x가 들어갈 수 있는 가장 왼쪽 인덱스를 반환한다.
  • x가 이미 존재하면 그중 가장 왼쪽 위치를 가리킴.

• bisect_right(arr, x)

  • x가 들어갈 수 있는 가장 오른쪽 인덱스를 반환한다.
  • x가 이미 존재하면 그 오른쪽 다음 인덱스를 가리킨다.

import bisect

arr = [1, 3, 3, 3, 5, 7]
x = 3
left = bisect.bisect_left(arr, x)  # 1
right = bisect.bisect_right(arr, x) # 4

bisect_left, bisect_right는 실제 코딩테스트에도 자주 나와서 직접 구현해보고 기억해두는것도 좋은 팁이다.

function bisect_left(arr, target) {
  let left = 0, right = arr.length;
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] < target) left = mid + 1;
    else right = mid;
  }
  return left;
}

function bisect_right(arr, target) {
  let left = 0, right = arr.length;
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] <= target) left = mid + 1;
    else right = mid;
  }
  return left;
}

// 예시 사용법
const arr = [1, 3, 3, 3, 5, 7];
console.log(bisect_left(arr, 3));  // 출력: 1
console.log(bisect_right(arr, 3)); // 출력: 4

이처럼 bisect는 중복 값의 구간이나, 삽입 위치 찾기 등에 매우 효과적이다.
이진 탐색의 개념을 확장하여, 탐색뿐 아니라 빠른 위치 계산에도 활용한다.

이분 탐색이 쓰이는 대표 사례

• 빠른 값 탐색: 정렬된 배열/리스트에서 특정 값 찾기
• 최적화 문제: 답의 범위가 일정할 때 답을 이분으로 줄여가며 결정
• lower/upper bound 찾기: 값의 구간 및 조건 만족 최적값 계산

이분 탐색은 정렬된 데이터에서 빠른 탐색 성능이 필요할 때 반드시 쓰이는 핵심 알고리즘이다.
파이썬의 bisect 모듈, 직접 구현 등을 통해 다양한 문제에 적용 가능하다.