본문 바로가기

# Foundation/알고리즘

이분탐색(Binary Serach) 알고리즘


 이분탐색이란?

매 단계마다 탐색범위를 절반씩 줄이는 방식.

현재범위를 반으로 쪼갠 뒤, 답이 존재하지 않는 쪽을 제거한다.


업 다운 게임이 대표적인 예시인데,

범위가 [0, 100]인 게임에서 최소횟수로 정답을 맞추려면,


정답이 있을법한 구간의 중간값을 골라서, 

매번 정답의 범위를 절반으로 줄여야 한다.


UP 이라면, 작은 구간에는 답이 없으며.

DN 이라면, 큰 구간에는 답이 없다.




 이분탐색의 제약

이분탐색의 핵심은 정답이 없는 절반을 배제하는 것 이며,

배제할 구간에 정답이 없다는 것을 확신할 수 있어야 한다.


업-다운 게임에서 이분탐색을 적용할 수 있는 이유는.

50의 결과가 UP일때, 

50이하에는 정답이 없다고 확신할 수 있기 때문이다.


중간값과의 비교를 통해 답의 위치를 알 수 있어야 하며

수학적으로 풀어보면, 단조성을 갖는 함수나 배열에만, 

이분탐색을 적용할 수 있다.



  • 단조성(Monotonicity)

값이 유지되거나 증가 또는 감소하는 성질. (Monotonic increase/decrease)

값이 순수하게 증가, 감소만 하는 경우 Strict 하다고 한다.   (Strictly increase/decrease)




 이분탐색의 해 찾기

  • STEP 1 : 비교함수를 정의하자

구간의 중간값과 찾는 값의 비교(Comparison)를 통해 이분탐색이 이루어지는데,

어떤 방식으로 비교할건지, 비교함수 test(x) 를 정의해야 한다.


비교함수는 true 또는 false를 반환해야만 하며.

이것으로 답의 상대적인 위치를 파악할 수 있어야 한다.

즉, 찾고자 하는 값의 경계면 에서 true / false가 반전되어야 한다.


예를 들어, 첫 번째 17을 찾는 비교함수는 다음과 같이 정의할 수 있다.

16, 17을 경계면으로 true / false가 반전되기 때문이다.

int N[];

bool test(int x){
        return 17 <= N[x];
}


  • STEP 2 : 최초구간을 설정하자.

구간이 너무 긴 경우, 시간만 낭비된다.

구간이 너무 짧은 경우, 정답이 버려질 가능성이 있다.


구간을 최대한 짧게하되,  

정답이 버려지지 않도록 유의하자.



  • STEP 3 : 절반씩 잘라가면서 임시정답(ANS)을 갱신한다.

이제서야 절반씩 잘라가면서 이분탐색을 진행하는데.

경계면의 우측구간(true section)에 접근할 때 마다 임시정답을 갱신한다. 


즉, 비교함수가 true일 때 마다, 임시정답을 갱신하고 다시 진행해야 하는데.

만약 17을 찾았더라도 탐색을 멈추면 안된다.

아직 좌측에 첫 번째 17이 있을 가능성이 있기 때문이다.


이 과정을 계속 반복하면, 임시정답은 경계면에 조금씩 가까워지며.

경계면에서 가장 가까운 첫 번째 true의 인덱스를 얻게된다.


이 때, 아래의 그림에 인덱스 9가 나타난 것에 유의하자.

표준 라이브러리에서 쓰이는 구간은 모두 반닫힌 구간이다. //   [  )







  • STEP 4 : ANS의 유효성을 검사한다.

이분탐색이 종료되었다면,  

배열 또는 함수의 상황에 따라 케이스가 나뉜다.

  1. 17이 존재하는 경우.

    경계면에서 가장 가까운 true가 17이다.
    첫 번째 17을 성공적으로 찾았다.


  2. 17이 없지만, 17보다 큰 값은 존재하는 경우.

    경계면에서 가장 가까운 true가 17이 아니다.
    임시정답은 갱신되었지만, 실제로는 값을 못찾은 경우와 같다.
    정답이 실제 우리가 원하는 값인지 체크하는 과정이 필요하다.


  3. 17도 없지만, 17보다 큰 값도 없는 경우.

    임시정답이 한번도 갱신되지 않으므로, 기본값인 상태에서 멈춘다.
    이 경우에는 기본값을 9로 해두면 해결된다.



 해 구간의 길이 찾기

  • STEP 1 : lower_bound를 찾자


16, 17을 경계면으로 갖는 비교함수를 사용하여.

17의 lower_bound를 찾는다.


단, 얻어진 값이 실제로 17인지 체크해야 한다.



  • STEP 2 : upper_bound를 찾자


17, 18을 경계면으로 갖는 비교함수를 사용하여.

17의 upper_bound를 찾는다.



  • STEP 3 : 길이를 구하자


17의 upper_bound에서 lower_bound를 빼면 개수가 나온다.



     std:: lower_bound / upper_bound

    C++의 <algolihtm> 헤더에서 lower_bound, upper_bound 함수를 제공한다.

    정수를 찾을때만 적용할 수 있다.


    유의해야 할 사항은 다음과 같다.

    • 구간의 표현은 [start, end)로 해야할 것.

    • lower_bound로 찾은 값은, 그 값이 아닐 수 있음.

    • 오른쪽 구간이 없다면 자동으로 end를 반환한다.


    // lower_bound/upper_bound example
    #include <iostream>         // std::cout
    #include <algorithm>        // std::lower_bound, std::upper_bound, std::sort
    #include <vector>           // std::vector
    
    int main () {
            int myints[] = {10,20,30,30,20,10,10,20};
            std::vector<int> v(myints,myints+8);                   // 10 20 30 30 20 10 10 20
    
            std::sort (v.begin(), v.end());                                // 10 10 10 20 20 20 30 30
    
            std::vector<int>::iterator low,up;
            low=std::lower_bound (v.begin(), v.end(), 19); //                  ^
            up= std::upper_bound (v.begin(), v.end(), 20); //                                   ^
    
            std::cout << "lower_bound at position " << (low- v.begin()) << '\n';
            std::cout << "upper_bound at position " << (up - v.begin()) << '\n';
    
            return 0;
    }
    

    lower_bound at position 3

    upper_bound at position 6



       실수 도메인에서 이분탐색하기

      • 횟수를 제한

      실수 도메인에서 이분탐색은 종료되지 않기 때문에,

      탐색횟수에 제한을 걸어야 한다.


      이분탐색이 진행될 때 마다, 임시정답은 경계면에 가까워지며.

      갱신될 때 마다, 정답과의 상대오차는 절반수준으로 줄어든다.


      50번 정도 반복하면,  정답에 매우 가까운 근사값을 얻을 수 있을 것 이다.

      실수 도메인 문제에서는,  근사값을 구하라는 방식으로 출제된다.



       관련 문제

       

      1920번: 수 찾기

      첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수들의 범위는 int 로 한다.

      www.acmicpc.net

       

      2805번: 나무 자르기

      문제 상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기을 이용해서 나무를 구할것이다. 목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따

      www.acmicpc.net

       

      1654번: 랜선 자르기

      첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 후 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 정수로 입력된다. 랜선의 길이는 231-1보다 작거나 같은 자연수이다.

      www.acmicpc.net

       

      10816번: 숫자 카드 2

      첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이가 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이수도 -10,00

      www.acmicpc.net