이진탐색 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로 접근해 보자.