java arrays binarysearch 함수를 알아봅시다.

 Arrays의 BinarySearch는 정렬된 배열에서 이진 탐색을 할 수 있습니다. 저는 여태까지 자바의 바이너리 서치가 값이 없으면 단순히 -1을 리턴하는 줄 알고 잘 써먹지 않았습니다. 그런데, 설명을 보니 그러지 않아도 되겠다는 것을 알 수 있었습니다.

 

---

 공식 설명을 먼저 보겠습니다.

 

 이 메서드는 아시다시피, sorted가 되어야 동작하는 알고리즘입니다. 리턴 값에 대한 설명을 봅시다.

 

 해당 key를 찾으면 그 위치를 리턴하고, 그렇지 않으면 -Insertion point-1 값을 리턴합니다. Insertion point가 어떻게 정의되는지도 위에 나와 있는데요. key보다 greater한 최초의 위치라고 되어 있어요. 이는 Collections의 binarySort나 Arrays의 binarySort나 똑같습니다. 쉬운 이해를 위해서 그림을 가지고 설명해 보겠습니다.

 

 {1, 3, 4, 7, 9}는 정렬된 배열입니다. 여기서 3을 찾는다고 하면 1을 리턴합니다. 왜냐하면, 3은 있기 때문입니다.

 

 

 4를 찾는다고 하면 2를 리턴할 겁니다. 4도 배열에 있기 때문입니다.

 

 

 그런데 binarySearch에 6을 찾을 키 값으로 넘기면 어떻게 될까요? 이 때에는 6보다 큰 최초의 위치를 찾습니다. 보니까 3이였습니다. 여기에 -1을 곱하면 -3이고 1을 빼면 -4입니다. 따라서 -4를 리턴합니다.

 

 

 Insertion location이 와닿지 않는 경우도 있으실 텐데요. 6을 3번째 위치에 넣고 나머지를 뒤로 밀어버리면 sorting이 된 상태 그대로 유지됨을 알 수 있어요. 키가 없을 때에는 어느 위치에 넣어야 sorting 상태가 유지되는지 찾은 다음에, 그 위치에 -1을 곱하고 1을 빼게 됩니다. 이제 {1, 3, 4, 7, 9}에서 10을 찾으려고 하면 어떻게 될까요?

 

 10은 없는 위치입니다. 그러면 {1, 3, 4, 7, 9}에서 어느 위치에 넣어야 정렬 상태가 유지될까요? 5일 겁니다. 따라서, Insertion 위치는 5가 되고, 여기에 -1을 곱하고 1을 뺀 값은 -6이 됩니다. 리턴 값에 대한 설명이 끝났으니 예제를 봅시다.

 

 arr은 위에서 설명한 {1, 3, 4, 5, 7} 배열입니다. 7번째 줄부터 8번째 줄 까지는 키 값으로 i를 넣었을 때, binarySearch의 리턴값을 출력합니다. 아래 결과는 프로그램의 실행 결과입니다.

 

 

 여기서, 0보다 작은 결과가 나온 수들은 배열에 없던 수입니다. 어떻게 음수 값이 나왔는지 하나 하나 따져보시면 도움이 될 듯 합니다.

 

---

 이런 걸 어디에 써 먹을 수 있는가? 당연하게도 좌표 압축을 할 때 써먹을 수 있습니다. 보통 좌표 압축을 할 때에는 중복도 같이 제거를 하게 되고요. 어떻게 하는지는 어렵지 않게 생각하실 수 있으리라 생각이 듭니다. 중복이 제거된 정렬된 리스트에서 lower_bound와 upper_bound를 구현할 수 있습니다.

 

 lo를 binarySearch의 리턴값이라 했을 때, 10번째 줄에 lo가 0인 경우에는 (lo + 1)에 -1을 한다고 되어 있어요. 역산을 한 셈인데요. x가 배열에 없을 때, 키가 k보다 큰 최초의 위치를 x라고 했다면 x에 -1을 곱한 다음에 1을 빼 버렸습니다. 이것이 -x-1이였습니다. 이 값이 바이너리 서치 메서드의 리턴 값인 lo였단 말이죠.

 

 우리는 x를 구하는 게 목적입니다. -x-1의 값이 lo이므로, x의 값은 -lo-1입니다. 이를 적당히 묶어주면 -(lo + 1)이 됩니다. x가 없다면, x보다 크거나 같은 최초의 위치나, x보다 큰 최초의 위치나 같습니다. 그렇지 않으면 어떨까요?

 

 

 7보다 크거나 같은 최초의 위치는 3이지만, 7보다 큰 최초의 위치는 4입니다. 즉, lower_bound와 upper_bound가 1이나 차이나게 됩니다. 이 부분을 잘 구현해 주시면 됩니다.

 

 

 실행 결과는 위와 같습니다. 시간 복잡도는 log(이진 탐색을 수행할 배열의 길이)에 비례합니다.

 

---

 그런데, 키가 unique 하지 않은 경우에는 binary_search 함수를 가지고 깡 lower_bound, upper_bound 등을 수행할 수 없어요. 이는 키를 찾았을 때, 키를 찾은 위치를 리턴해 버리기 때문이에요. 이걸 어떻게 해야 하죠? 키가 unique 하지 않다면 (key, location) 쌍으로 만들고 나서, binary_search를 걸어버리면 됩니다.

 

 lo는 unique 하기 때문에 (x, lo)를 묶은 것 또한 unique 하다는 게 핵심이에요. x를 1번째 기준 오름차, lo를 2번째 기준 오름차로 정렬하려면 아래와 같이 compareTo를 구현하시면 됩니다.

 

 

 어렵지 않죠? 다음에, 키 x의 lower_bound를 찾는다면 어떻게 해야 할까요? lo를 아래와 같이 채워 넣었다면 당연하게도 -1보다는 클 거고 unique 할 겁니다.

 

 당연하게도 -1보다는 크겠죠? 따라서, 키 값 k로 두고 lo값 -1로 두면 키 값을 찾을 수 없으므로, - insertion point - 1이 리턴되게 됩니다. - x - 1을 R이라 하면, x 값을 찾아야 하는 꼴입니다. -(R + 1) 값이 x이므로, lower_bound 함수를 아래와 같이 작성하시면 됩니다.

 

 

 핵심은 해당 키 값의 위치까지 같이 넣었다는 것입니다. x의 upper_bound를 찾기 위해서는 lower(li, x+1)을 호출하시면 됩니다.