이진탐색 Binary Search, Lower/Upper Bound, Parametric Search
이진 탐색 : O(logn)
개념
Binary search는 정렬된 array에서 어떤 값 k를 찾는 방법이다. 이 또한 divide and conquer를 사용하는 방식으로, 재귀방정식을 세우면 아래와 같다.
$T\left(n\right)\ =\ T\left(\frac{n}{2}\right)\ +\ c$
따라서 시간복잡도는 O(logn).
다른 방식으로,
처음 n개를 탐색할 때, 중앙값을 보고 탐색할 부분을 절반으로 나눈다.
다음 n/2개를 탐색할 때, 중앙값을 보고 탐색할 부분을 절반으로 나눈다.
...
마지막 것이 탐색된다.
즉, n개의 input이 있을 때 탐색은 logn번 진행한다.
반복문으로 탐색 : O(logn)
int search(vector<int>& v, int input){
int start = 0, end = v.size()-1, mid;
while(start <= end){
mid = (start + end) / 2;
if(v[mid] < input){
start = mid + 1;
} else if(v[mid] == input){
return mid; // found
} else{
end = mid - 1;
}
}
return -1; // not found
} 코드의 핵심은
- v는 정렬되어 있어야 한다
- start <= end까지 반복
- mid가 더 작은 경우 -> end를 mid-1로 당김
- mid가 더 큰 경우 -> start를 mid+1로 당김
STL 이용 : O(logn)
단순 해당 값이 있는지 없는지만 찾으려면 STL을 사용하는 것이 더 편리할 것이다.
template <class ForwardIterator, class T>
bool binary_search (ForwardIterator first, ForwardIterator last, const T& val)
binary_search(v.begin(), v.end(), value);
Lower Bound, Upper Bound : O(logn)
lower bound는 'array에서 탐색하는 값 k보다 크거나 같은 값이 처음 나오는 위치'이고, upper bound는 'array에서 탐색하는 값 k보다 큰 값이 처음 나오는 위치'이다. 이 용어들은 자주 사용하니 기억해 두자.
반복문으로 탐색
int lower_bound(vector<int> &v, int target)
{
int mid, start = 0, end = v.size();
while (start < end)
{
mid = (start + end) / 2;
if (v[mid] >= target) // 중간값이 target보다 크거나 같은 경우 해당 index까지 end를 당김.
end = mid;
else start = mid + 1; // 중간값이 target보다 작으면 mid+1까지 start를 당김.
}
return end;
}
int upper_bound(vector<int> &v, int target)
{
int mid, start = 0, end = v.size();
while (start < end)
{
mid = (start + end) / 2;
if (v[mid] > target) // 중간값이 target보다 큰 경우 해당 index까지 end를 당김.
end = mid;
else start = mid + 1; // 중간값이 target보다 작으면 mid+1까지 start를 당김.
}
return end;
} 코드의 핵심은
- start < end까지 반복
- 더 작은 값을 탐색해야 하면 end = mid
- 더 큰 값을 탐색해야 하면 start = mid + 1
- lower bound의 경우 크거나 같은 값을 찾으므로 조건문은 >=, upper bound의 경우 큰 값을 찾으므로 조건문은 >. 이를 좀 더 쉽게 이해하는 방법은, [if문 안에 있는 조건을 민족하는 제일 작은 index를 찾는다]고 생각하면 된다. Lower bound의 경우 target보다 크거나 같은 값 중 제일 작은 index를, upper bound의 경우는 target보다 큰 값 중 제일 작은 index를 찾는 것이다.
- 만약 arr에 없는 값을 탐색 할 시엔은 v.size()값을 가지는 end가 리턴됨.
STL 이용 : O(logn)
lower_bound(v.begin(), v.end(), value); // 결과로 iterator가 리턴됨
lower_bound(v.begin(), v.end(), value) - v.begin(); // index
upper_bound(v.begin(), v.end(), value); // 결과로 iterator가 리턴됨
upper_bound(v.begin(), v.end(), value) - v.begin(); // index만약 해당하는 값이 없으면 .end()를 리턴한다.
Parametric Search
optimization problem을 decision problem으로 바꿔 푸는 것. '전체 중에서 최적해를 찾는 문제(optimization problem)'를 '특정 값은 답(해)이 될 수 있는가?(decision problem)'로 바꿔 풀겠다는 것이다. 그리고 이분 탐색과 마찬가지로 그 '특정 값'이 해가 되냐, 그렇지 않냐에 따라 다음으로 찾을 범위를 바꾼다. 이분 탐색과 유사하게 풀 수 있다는 것이다.
(보편적으로) parametric search로 풀어야 하는 문제들은 최적화 문제로써 풀기는 어렵지만
- 정답이 속한 집합의 크기가 long long, 또는 int과 같이 크지만
- 결정 문제로 바꾸었을 때(특정 값은 답이 될 수 있는가?) 쉽게 풀리며
- 가능한 답이 연속적(정수) - 부연 설명을 하자면 예를 들어, 최댓값을 구하는 문제의 경우 어떤 값 k가 조건을 만족한다면 k보다 작은 모든 수들은 조건을 만족해야 한다는 것 -
위 특징들이 있으며, 이러한 문제가 있다면 parametric search로 접근해 보자.