이분 탐색(Binary Search)

이분 탐색(Binary Search)은 정렬된 배열에서 원하는 값을 O(log N) 시간에 빠르게 찾는 알고리즘이다. 배열을 절반씩 나누면서 탐색하기 때문에 선형 탐색(O(N))보다 훨씬 빠르다.

핵심 조건
1. 탐색할 데이터가 정렬되어 있어야 한다
2. 범위를 반씩 줄이면서 탐색한다

알고리즘	시간 복잡도	설명
선형 탐색	O(N)	모든 요소를 순차 탐색
이분 탐색	O(log N)	매 단계마다 탐색 범위를 절반으로 줄임
투포인터	O(N)	양쪽 포인터를 이동하며 탐색

동작 방식

1. 배열의 중간 인덱스(mid)를 계산한다.
2. target과 중간값을 비교한다.

• 같으면 → 탐색 성공
• 작으면 → 왼쪽 구간 탐색 (high = mid-1)
• 크면 → 오른쪽 구간 탐색 (low = mid+1)

3. 찾거나 탐색 범위가 끝날 때까지 반복

예시

정렬된 배열에서 7을 찾는 경우

arr = [1, 3, 5, 7, 9, 11, 13]
target = 7

1. low=0, high=6 → mid=3 → arr[3]=7 → 찾았다

만약 target이 9라면

1. mid=3 → 7 < 9 → 오른쪽 탐색
2. mid=5 → 11 > 9 → 왼쪽 탐색
3. mid=4 → 9 → 찾았다

Java 구현 예시

public class BinarySearchExample {

    // 이분 탐색 기본 구현
    public static int binarySearch(int[] arr, int target) {
        int low = 0;
        int high = arr.length - 1;

        while (low <= high) {
            int mid = (low + high) / 2;

            if (arr[mid] == target) {
                return mid; // 탐색 성공
            } else if (arr[mid] < target) {
                low = mid + 1;  // 오른쪽 탐색
            } else {
                high = mid - 1; // 왼쪽 탐색
            }
        }

        return -1; // 찾지 못하면 -1
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11, 13};
        System.out.println(binarySearch(arr, 7));  // 3
        System.out.println(binarySearch(arr, 9));  // 4
        System.out.println(binarySearch(arr, 2));  // -1
    }
}

조건을 만족하는 최솟값 찾기 (Lower Bound)

코딩 테스트에서는 단순히 값 존재 여부만 확인하지 않고 "조건을 만족하는 가장 작은/큰 값"을 찾을 때 이분 탐색을 활용한다.

예: 배열에서 target 이상인 첫 번째 값(=Lower Bound) 찾기

public static int lowerBound(int[] arr, int target) {
    int low = 0;
    int high = arr.length;
    
    while (low < high) {
        int mid = (low + high) / 2;
        if (arr[mid] < target) {
            low = mid + 1; // target보다 작으면 오른쪽
        } else {
            high = mid;    // target 이상이면 왼쪽 포함
        }
    }
    return low; // target 이상 첫 번째 인덱스
}

arr = [1, 3, 5, 7, 9, 11, 13]

target = 6 → lowerBound = 3 (7이 첫 번째로 6 이상)
target = 10 → lowerBound = 5 (11이 첫 번째로 10 이상)

투포인터(Two Pointers)

이분 탐색과 함께 자주 쓰이는 투포인터는 정렬된 배열에서 양 끝의 포인터를 이동하며 조건을 만족하는 구간을 찾는 방식이다.

1. left를 0, right를 배열 끝에서 시작
2. 조건에 따라 두 포인터를 이동
3. O(N) 시간 안에 구간/쌍을 탐색 가능

int left = 0, right = arr.length - 1;
while (left < right) {
    int sum = arr[left] + arr[right];
    if (sum == target) break;
    if (sum < target) left++;
    else right--;
}

이분 탐색 vs 투포인터

구분	이분 탐색	투포인터
시간 복잡도	O(log N)	O(N)
전제 조건	정렬된 데이터	정렬된 데이터
탐색 방식	범위를 절반씩 줄임	양쪽 포인터를 이동하며 탐색
사용 예시	특정 값/최솟값/최댓값 찾기	구간 합, 두 수의 합, 슬라이딩 윈도우
적합한 문제 유형	단일 값 또는 조건 판별	구간/쌍/연속된 부분 배열 탐색

📝 느낀점

이분 탐색을 다시 정리하면서 단순히 값을 찾는 문제뿐만 아니라 조건을 만족하는 최솟값/최댓값을 찾는 문제에서 활용도가 높다는 것을 깨달았다. 특히 Lower Bound와 Upper Bound 개념을 명확히 이해하면 코딩 테스트에서 범위 탐색, 최적화 문제를 효율적으로 풀 수 있다.

또한, 투포인터와 함께 사용하면 정렬된 배열 기반의 탐색 문제를 O(N) 또는 O(log N) 수준으로 빠르게 처리할 수 있어 앞으로 대량의 데이터 탐색이나 조건 검색을 구현할 때도 유용하게 쓸 수 있을 것 같다.