이진탐색, upper_bound , lower_bound

이진탐색이란 배열의 내부가 정렬되어있어야 사용할수있는 탐색이다.

 

이진탐색은 시작점, 끝점, 중간점을 반복 이용하여 중간점과 찾고자하는값을 비교하며 데이터를 찾는다. 

 

또한 탐색을 진행할때마다 평균적으로 확인하는 원소가 절반으로 줄어든다. 즉, 빅오 표기법에 따라 O ( logn) 의 복잡도를 가진다.

 

간단한 이진탐색을 구현하는 방법은 재귀,반복을 이용하는 두가지 방법이 있는데 반복을 이용하는 코드는 다음과 같다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector <int> list;
int binarySearch(vector <int> &list , int left, int right ,int target){
    while (left<= right){
       int mid = (left + right) /2;
       if(list[mid] == target){
           return mid;
       }
       else{
           if(list[mid] < target){
               left = mid +1;
           }else{
               right = mid -1;
           }
       }
    }
    return -1;
}

int main(){
    int N, target;
    cin >> N >> target;
    for(int i = 0 ;i < N ; i++){
        int input;
        cin >> input;
        list.push_back(input);
    }
    sort(list.begin(), list.end());
    int ansIndex = binarySearch(list,0,N-1,target);
    
    if(ansIndex == -1){
        cout << "찾을수없습니다." ;
    }
    else{
        cout << ansIndex;
    }
}

 

만약, 정렬되어있는 배열에서 특정 원소의 갯수를 구하고자 하면 어떻게 하면될까?

 

이 또한 이진탐색을 이용하여 구할수있다.

 

다만 위의 코드로 이진탐색을 구현하지않고, c++에서 제공하는 함수를 통하여 더 간단하게 구할수있다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N , target;
vector <int> list;

int countByRange(vector<int>& v, int leftValue, int rightValue) {
    vector<int>::iterator rightIndex = upper_bound(v.begin(), v.end(), rightValue);
    vector<int>::iterator leftIndex = lower_bound(v.begin(), v.end(), leftValue);
    return rightIndex - leftIndex;
}
int main(){
    cin >> N >> target;
    for(int i= 0 ; i < N; i++){
        int x;
        cin >> x;
        list.push_back(x);
    }
    sort(list.begin() , list.end() );
    cout << countByRange(list, target ,target);

    return 0;
}

 

위의 코드에서 lower_bound 란 "원하는 값 K 이상이 처음 나오는 위치" 를 찾는 함수이며,

upper_bound 의 경우 "원하는 값 K 가 처음 초과 되는 위치" 를 찾는 함수이다.