[C++/STL] 이분탐색(이진탐색) 관련 함수

이분탐색(이진탐색)이란?

상대방이 속으로 생각한 숫자를 찾는 '업다운' 게임의 규칙은 다음과 같다. 상대방은 제한된 범위 안에서 숫자를 생각하고 또 다른 사람은 숫자를 부르며 그 숫자보다 생각한 수가 크면 업, 작으면 다운으로 상대방이 생각한 수를 맞추는 게임이다.

이분탐색은 '업다운' 게임과 같이 배열의 가장 중간의 값을 선택하고 그 수가 우리가 찾는 수보다 크면 중간 위치 부터 마지막 위치까지, 작으면 처음 위치부터 중간 위치까지를 반복하여 탐색 범위를 좁혀가며 원하는 수를 찾는 방법이다.

 

하지만 이를 위해서는 무조건 배열의 오름차순 정렬이 선행되어야 한다.

 

그리고 이런 이분탐색을 친절하게도 STL에서 제공한다.

algorithm.h 를 코드에 추가하면 아래 함수들을 사용할 수 있다.

---

1. binary_search

bool binary_search(start_idx,end_idx,val)

 

입력 값

start_idx : 시작 포인터

end_idx : 마지막 포인터

val : 찾고싶은 값

 

반환 값

bool : 일치하는 val 이 있다면 true, 없다면 false

 

2. upper_bound

upper_bound (start_idx,end_idx,val)

 

입력 값

start_idx : 시작 포인터

end_idx : 마지막 포인터

val : 찾고싶은 값

 

반환 값

일치하는 값이 있다면 그 중에서 가장 처음에 있는 주소를 반환한다.

없다면 마지막 위치를 반환한다.

 

3. lower_bound

lower_bound(start_idx,end_idx,val)

 

입력 값

start_idx : 시작 포인터

end_idx : 마지막 포인터

val : 찾고싶은 값

 

반환 값

일치하는 값이 있다면 그 중에서 가장 마지막에 있는 주소를 반환한다.

없다면 마지막 위치를 반환한다.

 

---

위 세 함수를 코드로 확인해보자

STL은 템플릿으로 만들어져있어 배열,컨테이너 모두 사용 가능하다. (개꿀..)

 

#include <vector>
#include <algorithm>
#include <iostream>

int main()
{
    vector<int> vec;
    int arr[30];
      
    for(int i = 9; i >= 0; i--)
    {
    	int t = 3;
	while(t--)
        {
            vec.push_back(i);
    		arr[i] = i;
        }

    }
    
    sort(vec.begin(),vec.end());
    sort(arr,arr+10);
    
    //vector
    cout<< binary_search(vec.begin(),vec.end(),10) <<endl;
    cout<< binary_search(vec.begin(),vec.end(),1) <<endl;
    
    cout<< upper_bound(vec.begin(),vec.end(),10) <<endl;
    cout<< upper_bound(vec.begin(),vec.end(),1) <<endl;
    
    cout<< lower_bound(vec.begin(),vec.end(),10) <<endl;
    cout<< lower_bound(vec.begin(),vec.end(),1) <<endl;
    
    //array
    cout<< binary_search(arr,arr+10),10) <<endl;
    cout<< binary_search(arr,arr+10,1) <<endl;
    
    cout<< upper_bound(arr,arr+10,10) <<endl;
    cout<< upper_bound(arr,arr+10,1) <<endl;
    
    cout<< lower_bound(arr,arr+10,10) <<endl;
    cout<< lower_bound(arr,arr+10,1) <<endl;
    

}