이분 탐색 알고리즘 (Binary Search)
이분 탐색(Binary Search)은 정렬된 데이터에 한하여 탐색 범위를 두 범위로 나누어 특정 데이터를 탐색하는 방식입니다. 이분 탐색을 왜 쓰는지에 대해 알려면 먼저 선형 탐색에 대해 이해해야 합니다.
선형 탐색(Linear Search)은 말그대로 정렬 여부에 관계없이 앞부터 혹은 뒤부터 순차적으로 데이터를 탐색하는 방식입니다. 아래와 같은 정수 데이터가 나열되어 있다고 가정해봅시다.
이 데이터 배열에서 정수 2를 찾고자 합니다. 선형 탐색을 사용해 1부터 탐색하면 단 3번의 탐색 시도로 데이터를 찾아낼 수 있습니다. 하지만 만약 정수 7을 찾고자 한다면 선형 탐색을 사용하는 것은 너무나 비효율적으로 보입니다. 왜냐하면 7이 배열의 뒷부분에 있기 때문에 절반 이상의 데이터를 모두 탐색해야 하는 번거로움이 발생하기 때문이며 시간 복잡도가 높습니다.
그렇다면 범위를 두 부분으로 나누는 이분 탐색을 적용해 정수 7을 탐색해봅시다.
이분 탐색은 첫 탐색 위치를 배열의 가운데부터 시작합니다. 즉, 이 데이터 배열에서 데이터가 총 10개이기 때문에 이분 탐색은 10 / 2 = 5부터 탐색을 시작하여 찾으려는 데이터가 5와 같으면 바로 반환하고 그게 아니면 5보다 작은지 큰지에 따라 탐색 범위를 결정합니다. 정수 7은 5보다 크므로 5의 왼쪽 범위는 무시하고 5의 오른쪽 범위만 탐색합니다.
이제 오른쪽 범위에서 탐색 위치를 가운데 데이터인 8로 시작하고 8보다 작은지 큰지 확인합니다. 찾으려는 데이터가 더 작으므로 8의 왼쪽 범위를 탐색합니다.
이제 왼쪽 범위에서 탐색 위치를 가운데 데이터인 6으로 시작하고 6보다 작은지 큰지 확인합니다. 찾으려는 데이터가 더 크므로 6의 오른쪽 범위를 탐색합니다.
가운데 위치에서 데이터 7을 찾아냈습니다. 선형 탐색을 이용했다면 7번 탐색했을 일을 이분 탐색을 이용해 4번만에 탐색에 성공했습니다.
이러한 이유로 이분 탐색을 적용하면 데이터가 많은 배열에서 시간 복잡도를 크게 줄일 수 있는 장점이 있습니다.
알고리즘 구현
// Algorithm Analysis
// 이분 탐색 알고리즘 (Binary Search)
#include <iostream>
#define MAX 10
using namespace std;
int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int d = 7;
int binarySearch(int s, int e, int data) {
if (s > e) return -1;
int mid = (s + e) / 2;
if (arr[mid] == data) return mid;
else if (arr[mid] > data) return binarySearch(s, mid - 1, data);
else if (arr[mid] < data) return binarySearch(mid + 1, e, data);
}
int main() {
int idx = binarySearch(0, MAX - 1, d);
if (idx != -1)
cout << idx + 1 << "번째 index에서 발견"; // 7
}
시간 복잡도 : O(log N)
이분 탐색의 시간 복잡도는 O(log N) 입니다.
* 나동빈님 블로그를 참고하여 개인적으로 재작성한 글입니다.