이전에 설명한 순차 탐색 알고리즘보다 훨씬 좋은 성능을 보이는 이진 탐색(이분 탐색) 알고리즘이다. 영어로는 Binary Search Algorithm. 뜻에서 알 수 있듯이 숫자 2와 관련있는 알고리즘이다. 탐색 범위를 반 씩 줄여가며 탐색하기 때문에 이런 이름이 붙혀졌다.
다만 이 알고리즘은 한 가지 제약조건이 있다.
조건 : 저장된 데이터는 정렬되어 있어야 한다!
성능이 빠른데에는 역시 그만한 이유가 있다. 그렇다면 이제 간단한 원리에 대해 알아보자.
원리
탐색에는 언제나 지시자가 존재하는데, 이진 탐색의 경우에는 first, last, mid 3가지의 지시자가 존재한다.
위의 이미지처럼 7개의 데이터가 담긴 오름차순으로 정렬된 데이터에서 숫자 '3'을 탐색한다고 가정해보자. 첫 번재 탐색에서는 위의 그림처럼 first, last, mid 지시자가 정해진다.
first : arr[0]
last : arr[6]
mid : arr[(0+6)/2] = arr[3]
그리고 비교연산은 mid 지시자가 가리키는 데이터와 실시한다. 3을 찾고있는데 4가 잡혔다. 그렇다면 내가 찾는 원소 3은 mid 지시자보다 앞 칸에 존재한다는 것을 알게된다.
그리하여 last 지시자를 방금 전의 mid 위치의 한 칸 앞으로 땡기고, mid 지시자의 위치 또한 다시 계산한다.
first : arr[0]
last : arr[2]
mid : arr[(0+2)/2] = arr[1]
다시 mid 지시자가 가리키는 2와 내가 찾고자하는 3을 비교해보니 이번에는 3이 더 크다. 그렇다면 내가 찾는 3은 mid 지시자보다 오른쪽에 위치할 것이라는 것을 알 수 있다. 그럼 이번엔 first 지시자가 움직일 차례다.
그리하여 first 지시자는 mid보다 한 칸 뒤로 밀어졌다. 그리하여 first, last, mid 보다 같은 곳을 지시하게 된다. 이런 경우가 흔하게 발생하는 건 아니지만 이런 때도 있다. 보면 알겠지만 이렇게 되면 탐색은 이미 끝난 상황이다.
first = arr[2]
last = arr[2]
mid = arr[(2+2)/2] = arr[2]
mid 지시자가 가리키는 숫자가 드디어 내가 찾고자 하는 숫자가 되었다. 탐색이 완료되었다. 그렇다면 이제는 이걸 C++ 코드로 구현해보자.
구현
#include <iostream>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <functional>
using namespace std;
vector<int> v;
int BinSearch(int target)
{
int first = 0;
int last = v.size() - 1;
int mid;
while (first <= last)
{
mid = (first + last) / 2;
if (target == v[mid])
return mid;
else if (target < v[mid])
last = mid - 1;
else
first = mid + 1;
}
return -1;
}
int main()
{
cin.tie(NULL);
cout.tie(NULL);
ios::sync_with_stdio(false);
int size,temp;
cout << "Enter array size : ";
cin >> size;
for (int i = 0; i < size; i++)
{
cout << "v[" << i << "] : ";
cin >> temp;
v.push_back(temp);
}
sort(v.begin(), v.end());
int num;
cout << "\nEnter target value : ";
cin >> num;
cout << "Location : v[" << BinSearch(num) << "]\n\n";
return 0;
}벡터와 퀵소트를 이용하여 구현하였다. 위에 설명한 경우와 마찬가지로 오름차순으로 배열을 정렬한다.
실행결과
아주 잘 탐색한다. 함수를 조금 고치면 비교연산 순간을 출력시켜서 더 보기 좋게 만들 수도 있을 것이다.
