binary search / lower bound 그리고 upper bound 정리

바이너리 서치(binary search)

바이너리 서치는 아마 컴퓨터공학과 1~2학년이라면 자료구조시간이나 알고리즘 시간에 이름 한번쯤은 들어봤을 것이다.

그만큼 기본적이지만 강력한 알고리즘 중 하나이다. 

근데 요녀석은 정렬처럼 그냥 라이브러리 하나 호출해서 띡~ 하고 끝날때도 있는데, 뭔가 응용해야할 때가 간혹 있다.

 

대충 한번 정리해보자.

 

일단 바이너리 서치를 할려면 선행조건이 있다. 

정렬되어 있어야 한다는 점

 

그래서 중간에 하나 아무거나 짚어서 봐도 그 이전과 그 다음 값들이 어떨지 예상을 할 수 있는 것이다. 이를 이용해서 시간복잡도를 //(O(lgN)//)으로 줄일 수 있다.

 

일단그리고 C++ SLT에 binary_search라는 함수가 있다. 배열같은 컨테이너 시작과 끝 iterator를 넣고, 찾는 값을 넣으면 bool을 리턴해준다. 원하는 값이 있으면 true, 그렇지 않으면 false를 리턴한다.

 

근데 그러면 내가 찾는 녀석이 어디쯤에 존재하는지를 알 수가 없다.

그래서 보통 직접 구현해서 쓰곤 한다.

 

lower_bound와 upper_bound

근데 생각을 해 보자. 원래 배열이 잘 정렬되어 있긴 한데, 중복된 수가 있다면?

그리고 그 중복된 수가 몇 개인지를 알아야 하는 경우라면? 아니면, 그 중복된 수 모두를 체크해야 하는 경우라면 어떻게 해야할까?

 

위와 같이 중복이 있는 배열이라고 할 때, 모든 40을 다 찾아야 한다면 다음과 같이 lower bound와 upper bound를 이용하면 된다.

lower_bound(40)을 행하면 첫번째로 나타나는 40의 인덱스인 4를 리턴하고, upper_bound(40)을 행하면 마지막으로 나타나는 40의 인덱스 다음 값인 7을 리턴한다.

 

그러면 lower_bound부터 upper_bound까지 for-loop을 돌면 모든 40인 값들을 찾을 수 있다.

 

그렇다면 lower_bound(35)를 수행한다면? 35는 배열에 없는 값이다.

그러면 35가 들어갈 수 있는 4라는 인덱스를 똑같이 리턴한다. 4번자리는 기존 40이 있던 자리이다. 그러면 4번 자리에 35를 넣고, 기존 값들인 40, 50 등 을 한 칸씩 뒤로 밀면 35가 들어가도 전체 배열은 그대로 정렬된 상태를 유지하게 된다.

 

마찬가지로 그렇다면 upper_bound(35)를 수행한다면? 35는 배열에 없는 값인데, lower_bound(35)를 한 값과 마찬가지로 4라는 인덱스를 리턴한다. 마찬가지로 4번 자리에 35를 넣을 수 있다는 뜻이다.

 

배열에 없는 값에 대하여 lower_bound나 upper_bound 연산을 수행하면 같은 값이 나오게 된다.

이는 즉, 배열 안에 있는 x값의 개수를 찾고 싶다면 upper_bound(x) - lower_bound(x)라는 연산으로 할 수 있다.

 

그렇다면 그 정의는 다음과 같게된다.

lower_bound

- x라는 값을 배열에 넣을 때, 정렬된 상태를 유지하면서 넣을 수 있는 위치 중 가장 앞

(이때 넣는다는 개념은 해당 자리에 x를 넣고, 기존 값들은 다 1칸씩 뒤로 민다고 가정함)

- x라는 값 보다 같거나 큰 값 중 가장 앞에 있는 원소 위치

 

upper_bound

- x라는 값을 배열에 넣을 때, 정렬된 상태를 유지하면서 넣을 수 있는 위치 중 가장 뒤

- x라는 값보다 큰 값 중 가장 앞에 있는 원소 위치

 

 

 

---------------------------------------------------------------------

https://12bme.tistory.com/120

http://soen.kr/lecture/ccpp/cpp4/42-3-2.htm