Binary Search (이진 탐색)

 

이진 탐색(Binary Search)의 개념과 동작 방식

이진 탐색은 정렬된 배열이나 리스트에서 특정 값을 빠르게 찾기 위한 알고리즘이다. 일반적인 선형 탐색(linear search)은 처음부터 끝까지 하나씩 비교하기 때문에 최악의 경우 ⟨⟨O(N)⟩⟩의 시간이 걸린다. 반면, 이진 탐색은 탐색 범위를 절반씩 줄여가며 탐색하므로 시간 복잡도가 ⟨⟨O(log N)⟩⟩으로 훨씬 빠르다.

 

이진 탐색이 동작하려면 반드시 데이터가 정렬된 상태여야 한다. 정렬되지 않은 데이터에서 중간값과 비교해 탐색 범위를 결정하는 것은 의미가 없기 때문이다.

 

이진 탐색의 기본 동작 방식은 다음과 같다.

1. 배열의 ⟨⟨left⟩⟩와 ⟨⟨right⟩⟩ 인덱스를 설정한다.
2. ⟨⟨mid = (left + right) / 2⟩⟩ 값을 구한다.
3. ⟨⟨target⟩⟩과 ⟨⟨arr[mid]⟩⟩를 비교한다:
   • 같으면 탐색 성공 → mid 반환
   • 작으면 ⟨⟨right = mid - 1⟩⟩로 범위 축소
   • 크면 ⟨⟨left = mid + 1⟩⟩로 범위 축소
4. 범위가 유효한 동안(⟨⟨left <= right⟩⟩) 위 과정을 반복한다.

예를 들어 정렬된 배열 ⟨⟨[1, 3, 5, 7, 9]⟩⟩에서 값 5를 찾는다고 하면, 중간값 5를 바로 찾게 되므로 1회 탐색으로 끝난다. 만약 6을 찾는 경우는 두 번 비교 후 값이 없다고 판단할 수 있다.

 

---

시간 복잡도 비교: 선형 탐색 vs 이진 탐색

이진 탐색이 효율적인 이유는 매 탐색마다 범위를 절반으로 줄여간다는 점에 있다. 이 때문에 전체 데이터의 크기가 커질수록 탐색 횟수는 상대적으로 적어진다. 이 동작 원리를 기반으로 이진 탐색의 시간 복잡도는 ⟨⟨O(log N)⟩⟩이다.

예를 들어, 탐색 대상의 길이가 16일 경우 다음과 같이 탐색이 진행된다:

• 1회차: 16 → 절반으로 줄여 8
• 2회차: 8 → 4
• 3회차: 4 → 2
• 4회차: 2 → 1

이처럼 약 ⟨⟨log₂(16) = 4⟩⟩번만에 탐색이 종료된다.
이와 달리 선형 탐색(linear search)은 데이터 전체를 하나씩 확인하기 때문에 최악의 경우에는 ⟨⟨O(N)⟩⟩의 시간이 걸린다.

알고리즘	최악의 경우 시간 복잡도	특징
선형 탐색	⟨⟨O(N)⟩⟩	정렬 불필요, 단순 비교
이진 탐색	⟨⟨O(log N)⟩⟩	정렬 필수, 고속 탐색 가능

 

즉, 이진 탐색은 데이터가 많을수록 시간적인 이점이 급격히 커지는 알고리즘이다. 하지만 전제 조건이 정렬된 데이터라는 점이 항상 함께 따라온다. 정렬이 안 된 데이터라면, 우선 ⟨⟨O(N log N)⟩⟩ 시간의 정렬을 먼저 수행해야 이진 탐색의 장점을 누릴 수 있다.

---

이진 탐색의 구현 방식: 반복문과 재귀

이진 탐색은 두 가지 방식으로 구현할 수 있다. 하나는 반복문을 사용하는 방식이고, 다른 하나는 재귀 함수를 사용하는 방식이다. 두 방식 모두 본질적으로는 동일한 논리를 따르지만, 코드의 구조와 호출 방식에서 차이가 있다.

 

🔁 반복문 기반 이진 탐색

가장 많이 쓰이는 구현 방식으로, while 루프를 이용해 ⟨⟨left⟩⟩와 ⟨⟨right⟩⟩ 범위를 직접 조절한다.

public int binarySearch(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2; // 오버플로우 방지
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }

    return -1; // 찾지 못한 경우
}

이 방식은 스택을 사용하지 않고 루프만으로 처리하므로 메모리 사용이 적고, 대규모 데이터에도 안정적으로 동작한다.

 

🔁 재귀 기반 이진 탐색

재귀 방식은 논리적으로 더 직관적일 수 있지만, 재귀 호출의 깊이가 깊어지면 스택 오버플로우의 위험이 존재한다. 특히 재귀 호출이 깊어질 수 있는 환경(Java 등)에서는 주의가 필요하다.

public int binarySearchRecursive(int[] arr, int target, int left, int right) {
    if (left > right) return -1;

    int mid = left + (right - left) / 2;
    if (arr[mid] == target) return mid;
    else if (arr[mid] < target)
        return binarySearchRecursive(arr, target, mid + 1, right);
    else
        return binarySearchRecursive(arr, target, left, mid - 1);
}

재귀 호출을 반복 호출처럼 보이게 하면서도 코드가 간결해진다는 장점이 있지만, 실전 문제에서는 반복문 방식이 더 안정적이다.

 

💡 ⟨⟨mid = (left + right) / 2⟩⟩는 위험할 수 있다?

⟨⟨left⟩⟩ 와 ⟨⟨right⟩⟩의 값이 매우 클 경우, 단순히 둘을 더한 값이 정수의 범위를 초과하는 오버플로우가 발생할 수 있다. 이를 방지하기 위해 다음과 같이 중간값을 계산하는 것이 안전하다:

⟨⟨mid = left + (right - left) / 2⟩⟩