이 포스팅에서 소개할 내용은 다음과 같습니다.
1. Binary Search가 무엇인가.
2. 코드로 이해하는 Binary Search.
3. 문제로 이해하는 Binary Search.
4. Binary Search 응용 문제
1. Binary Search가 무엇인가.
이진탐색, 이원탐색, 이분탐색 등으로 불리는 Binary Search는 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘입니다.
이 때, Binary Search를 사용하려면 리스트가 오름차순으로 정렬되어 있어야 한다는 점을 주의해야 합니다.
위 그림처럼 정렬된 배열 a에서 특정한 값 x를 찾으려고 할 때, 첫번째 인덱스를 left, 마지막 인덱스를 right로, 가운데 인덱스를 middle로 설정합니다.
그 후, a[middle]의 값과 x값을 비교하는 작업을 수행합니다.
i) x < a[middle]
가운데 인덱스 값보다 x값이 작은 경우입니다. 이 경우, right의 값을 middle-1로 다시 설정하여 탐색을 반복합니다.
ii) x == a[middle]
가운데 인덱스 값과 x값이 같은 경우입니다. 이 경우, 탐색을 더 수행할 필요없이 middle을 리턴합니다.
iii) x > a[middle]
가운데 인덱스 값보다 x값이 큰 경우입니다. 이 경우, left의 값을 middle+1로 다시 설정하여 탐색을 반복합니다.
x의 값이 4라고 가정하자.
한 번 더 탐색했을 때의 결과는 위와 같습니다.
middle = (left + right)/2 이므로, 이 때 middle = (0+3)/2 = 1.5가 되는데, middle은 int형으로 선언하기 때문에 1로 간주합니다.
이 때도 마찬가지로 middle = 2 가 됩니다.
그 후, 탐색을 한 번 수행하게 되면 x == a[middle]이 되어 middle값이 리턴됩니다.
그렇다면 만약 x의 값이 정렬된 리스트 내에 존재하지 않는 경우는 어떻게 될까요?
x의 값을 4.5라고 간주합시다.
그럼 위의 상태에서 x > a[middle] 이 되어 left의 값이 middle+1로 바뀝니다. 즉, left는 3이 되고, middle은 다시 (3+3)/2 = 3이 됩니다.
그 후에 다시 탐색을 하게 되면, x < a[middle]이 되므로, right의 값이 middle-1이 되는데, 그렇게 되면 아래 그림과 같은 상황이 발생합니다.
즉, left가 right를 역전하는 상황이 발생하는 것입니다. 따라서 이렇게 역전이 됐다면 해당 리스트에 특정 x값이 없는 것으로 간주하면 됩니다.
2. 코드로 이해하는 Binary Search.
#include <iostream>
using namespace std;
int BinarySearch(int *a, const int x, const int left, const int right) {
if (left <= right) {
int middle = (left + right) / 2;
if (x < a[middle])
return BinarySearch(a, x, left, middle-1);
else if (x > a[middle])
return BinarySearch(a, x, middle+1, right);
else
return middle;
}
return -1;
}위의 코드에서는 오름차순으로 정렬된 배열의 참조값과 찾으려는 x의 값, 첫번째 인덱스, 마지막 인덱스를 인자로 받습니다.
해당 함수는 배열에서 x값을 찾을 수 없다면 -1을 리턴해줍니다.
x값을 찾았다면, x값이 들어있는 배열의 인덱스를 리턴해줍니다.
위 과정은 left가 right를 역전하기 전까지 수행되고, 만약 역전하게 된다면 배열에 x값이 없는 것으로 간주되어 -1이 리턴됩니다.
3. 문제로 이해하는 Binary Search.
해당 알고리즘을 이용하는 문제, BOJ_1920(수찾기)를 풀어보겠습니다.
#include <iostream>
#include <algorithm>
using namespace std;
int BinarySearch(int *a, const int x, const int left, const int right) {
if (left <= right) {
int middle = (left + right) / 2;
if (x < a[middle])
return BinarySearch(a, x, left, middle-1);
else if (x > a[middle])
return BinarySearch(a, x, middle+1, right);
else
return middle;
}
return -1;
}
int main() {
int num;
cin >> num;
int *arr = new int[num];
for (int i = 0; i < num; i++)
cin >> arr[i];
sort(arr, arr+num);
int xnum;
cin >> xnum;
int *xrr = new int[xnum];
int tmp = 0;
for (int i = 0; i < xnum; i++) {
cin >> xrr[i];
tmp = BinarySearch(arr, xrr[i], 0, num-1);
if (tmp != -1)
cout << 1 << endl;
else
cout << 0 << endl;
}
delete[] arr;
delete[] xrr;
return 0;
}참고로, 백준 내에서는 cin, cout 을 사용하게 되면 시간초과가 나기 때문에 scanf, printf 를 사용하시거나, ios::sync_with_stdio(false); cin.tie(nullptr);을 사용하시면 됩니다.
이상으로 Binary Search 알고리즘에 대한 설명을 마치겠습니다. 읽어주셔서 감사합니다!
4. Binary Search 응용 문제
