이분탐색(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번: 수 찾기

2805번: 나무 자르기

1654번: 랜선 자르기

10816번: 숫자 카드 2