[이진탐색] Binary Search, lower-bound, upper-bound

우리가 알고리즘을 할때 가장 단순하고도 쉽게 생각할 수 있는 것이 일일이 대조하면 찾는 순차탐색일 것이다.

순차탐색은 for으로 보통 구현되며 경우의 수 N과 M개의 경우에 시간복잡도 O(N*M)을 가진다.

즉, case가 적은 경우 문제될 것이 없으나 N과 M이 10000, 100000을 넘어갈 경우 부하가 심해진다.

 

때문에 우리는 이진탐색을 알아야한다. 시간복잡도가 logN으로 줄기 때문이다.

순차탐색은 보통의 경우 이진탐색으로 표현될 수 있다. 이진탐색의 기본 개념은 '분할정복'이다.

Divide & Conquer.

 

이진탐색은 3개의 parameter가 필요하다. 탐색하려는 start point, end point, 그리고 찾으려는 target.

이진탐색은 기본적으로 오름차순으로 정렬이 되어 있어야한다. 순서는 아래와 같다.

이진탐색 순서
1) 오름차순으로 정렬한다.
2) 가운데값 mid indx를 구하여 target과 비교한다.
3A) target < mid 이면, target이 mid보다 낮은 곳에 있으므로 탐색범위를 조정한다.
   오름차순이므로 mid index보다 상위 범위는 볼 필요가 없다.
   따라서, end point = mid-1 로 조정한다. start는 유지한다.
3B)  target > mid 이면, 반대로 mid의 하위 범위는 후보군에서 제외된다.
   따라서, start point = start -1로 조정한다. end는 유지한다.
4) target == mid면 탐색을 종료한다.
5) 과정을 반복한다.

 

이진탐색과정

아래의 배열이 있다. 3을 이진탐색으로 찾아보자.

1. s와 e, m을 각각 Start point, End point, Mid값이라고 하자. s가 0이고 e가 10이면 m은 5가 될 것이다.

우리가 찾는 target은 3이나, index m의 값은 6이다. 그럼 m보다 큰 범위는 탐색 후보에서 제외된다. 따라서 end point를 조정한다. end = mid - 1이 되어, e=4가 되겠다.

 

2. 이후 과정을 반복하면 m은 0+4/2로서 2가 되겠다. index 2의 값은 우리가 찾는 target의 값이다. 따라서 탐색을 종료한다.

 

 

이번엔 7을 찾아보자.

1. 위와 동일하게 m=5이나 index 5의 값은 6이나 우리가 찾는 값은 7이다. 그럼 mid의 하위 범위는 후보에서 탈락된다. 따라서, start point를 mid+1로 설정한다. s=6

2. s=6, e=10, m=8이게 된다. target보다 mid 8의 값이 9로서 크다. 그렇다면 mid 상위 범위는 후보에서 탈락된다.

따라서, end point를 mid-1로 설정한다. e=7

3. s=6, e=7, m=6이다. 이때 우리가 찾는 target값이 나왔다. 탐색을 종료한다.

 

 

이처럼 이진탐색을 탐색시마다 탐색범위가 절반으로 줄어들게 된다. 때문에 순차탐색보다 훨씬 빠르게 탐색할 수 있다.

사실 자료의 범위가 크지 않다면 성능차이가 크지 않지만 자료가 커질 수록 성능의 차이가 커지게 된다.

---

LowerBound, UpperBound

이진탐색을 응용하면 target이 시작하는 가장 작은 인덱스 값, 큰 인덱스 값을 구할 수 있다. 이를 각각 Lower bound, Upper bound라고 한다. 방법은 동일하나, 값을 찾고도 혹시 더 있을지 모르니 답 후보를 정해놓고 범위를 줄여 진행하는 것이 추가된다.

 

아래의 자료에서 target 1의 Lower bound를 구해보자.

1) s=0, e=10, m=5이다. mid 5의 값은 6이기때문에 탐색 범위를 아래로 줄인다. e= m-1는 4이다.

2) s=0, e=4, m=2이다. mid 2의 값은 1이다. 우리가 찾던 1이다. 때문에 mid 2를 lower bound라고 가정한 후 탐색 범위를 줄여 더 탐색해본다. 가장 작은 index를 찾는 것이니 mid아래로 범위를 줄여야겠다. 따라서 e=1이다.

3) s=0, e=1, m=0이다. 마찬가지로 mid 0도 우리가 찾는 값이다. mid 0을 답으로 다시 갱신한다. 추가적으로 반복하기 위해 범위를 조정하고 싶으나 e=-1이 되기 때문에 탐색할 수 없다.

4) 따라서 1의 lower bound는 0이 되겠다.

 

 

반대로 upper bound를 찾아보자.

1) s=0, e=10, m=5이다. mid 5의 값은 6이기때문에 탐색 범위를 아래로 줄인다. e= m-1는 4이다.

2) s=0, e=4, m=2이다. mid 2의 값은 1이다. 우리가 찾던 1이다. 이번에는 upper를 찾는 것이기 때문에 탐색 범위를 위로 해야한다. 따라서 답후보를 저장해 둔 후, start point를 조정한다.  s=mid+1이므로 3이 되겠다.

3) s=3, e=4, m=3이다. mid 3의 값은 1이므로 답 후보를 갱신한다. 추가로 반복하기 위해 start point를 mid+1인 4로 조정한다.

4) s=4, e=4이며 m도 4이다. 우리가 찾는 답보다 mid 4의 값은 크므로 end point 를 mid -1로 조정한다. 그러나 start point 보다 end point가 작아지므로 더이상 탐색을 하지 않고 종료한다.

5) 따라서 1의 upper bound는 3이 되겠다.

 

이처럼, lower 과 upper bound는 답 후보를 정하고 범위를 줄여나가는 식으로 진행하면 된다.