[이론/C++] 이분 탐색 (Binary Search)

이분 탐색(Binary Search)은 코딩 테스트에서 많이 등장하는 알고리즘 중 하나이다.

탐색 알고리즘 중 가장 기본적인 알고리즘으로, 특정 값을 빠르게 찾는 로직이다.

오늘은 이분 탐색에 대해 정리해보도록 하겠다.

 

---

이분 탐색이란?

 

이분 탐색(Binary Search): 정렬된 배열에서 탐색 범위를 절반씩 줄여나가면서 특정 값을 찾는 알고리즘

 

이분 탐색 알고리즘의 중요한 포인트는 정렬된 배열이 필요하다는 점이다.

왜냐하면 이분 탐색은 데이터가 정렬되었다는 가정 하에 동작하기 때문이다.

 

그렇다면 이분 탐색의 알고리즘이 어떻게 동작하는지 살펴보도록 하자.

 

 

 

---

이분 탐색의 원리

 

이분 탐색을 하기 위해서는 left, right, mid 3개의 위치값이 필요하다.

이분 탐색의 알고리즘은 다음과 같이 동작한다.

 

① 초기값은 left = 0, right = 배열 크기 - 1, mid = (left + right) / 2가 된다.

② 탐색값이 arr[mid] 보다 작다면 right = mid - 1로 설정한다.

③ 탐색값이 arr[mid] 보다 크다면 left = mid + 1로 설정한다.

④ 탐색값을 찾거나, left > right이 될 때까지 ② ~ ③을 반복한다.

 

 

 

예시를 통해 알고리즘의 흐름을 살펴보자.

정렬된 배열 {1, 3, 4, 6, 7, 8, 10, 13, 14} 에서 이분 탐색으로 4를 찾아보자.

 

 

 

 

left = 0, right = 8, mid = (0 + 8) / 2 = 4

4번째 요소(7)은 우리가 찾는 값(4)보다 크기 때문에 right = mid - 1로 설정한다.

 

 

 

 

left = 0, right = 3, mid = (0 + 3) / 2 = 1

1번째 요소(3)이 우리가 찾는 값(4)보다 작기 때문에 left = mid + 1로 설장한다.

 

 

 

 

left = 2, right = 3, mid = (2 + 3) / 2 = 2

2번째 요소(4)가 우리가 찾는 값(4)와 같기 때문에 종료한다.

 

 

 

---

이분 탐색은 언제 사용하는가?

 

이분 탐색 알고리즘은 탐색 알고리즘으로, 정렬된 배열에서 특정 값을 찾을 때 사용한다.

주로 입력값 N이 크거나, 최소값 혹은 최대값을 구할 때 사용한다.

 

절반씩 줄여나가며 탐색을 수행하기 때문에 시간 복잡도는 O(log N)이다.

이분 탐색은 탐색 알고리즘 중에서 많이 사용되는 알고리즘이기 때문에 꼭 알아두도록 하자.

C++ STL에서 이분 탐색 알고리즘인 'binary_search' 함수를 제공하고 있으니 참고

 

 

예시 문제: 백준 2343문제

https://www.acmicpc.net/problem/2343

 

정답 코드

#include <iostream>
#include <vector>

using namespace std;

int n, m, mx, l, r, mid, ans;
vector<int> v;

bool check(int size) {
    if (size < mx) return false;
    int cnt = 0, temp = size;
    for (int i = 0; i < n; i++) {
        if (temp < v[i]) {
            temp = size;
            cnt++;
        }
        temp -= v[i];
    }
    if (temp != size) cnt++;
    return cnt <= m;
}

int main() {
    cin >> n >> m; v = vector<int>(n, 0);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
        r += v[i];
        mx = max(mx, v[i]);
    }
    
    while (l <= r) {
        mid = (l + r) / 2;
        if (check(mid)) {
            r = mid - 1;
            ans = mid;
        }
        else l = mid + 1;
    }
    cout << ans;
    return 0;
}

 

 

 

---

정리

이분 탐색은 정렬된 배열에서 특정 값을 탐색하는데 매우 유용한 알고리즘이다. 코딩테스트 문제에서 자주 등장하는 개념이기 때문에 개념을 명확히 이해하고 구현할 수 있도록 해야 한다. 시간복잡도가 O(log N)이기 때문에 주어진 데이터 크기를 판단하여 빠른 탐색이 필요한 경우 사용하도록 하자.