이진 탐색 (Binary Search)
이진 탐색은 PS에서 정말 자주 쓰이는 알고리즘이다.
근데 알고는 있는데, 뭔가 자꾸 왼쪽.. 오른쪽.. 최대.. 최소.. 하면서 헷갈리게 된다.
글을 쓰고 나면 좀 이 헷갈림이 사라질까..
이진 탐색은 정렬된 데이터에서 특정한 값을 O(log N)시간에 찾기 위한 알고리즘이다.
데이터가 정렬되어져있기 때문에, 배열의 중간값과 찾으려는 값의 크기를 비교하면서 탐색하게 된다.
데이터가 오름차순으로 정렬됬다고 생각해보자. ( 1, 2, .... N )
그렇다면 다음의 두 명제는 자명할 것이다.
- 만약, 찾으려는 값이 중간값보다 크다면, 찾으려는 값은 중간값보다 오른쪽에 있을 것이다.
- 만약, 찾으려는 값이 중간값보다 작다면, 찾으려는 값은 중간값보다 왼쪽에 있을 것이다.
이 명제를 활용해 값을 찾는 방식이 이진 탐색이다.
이 방식을 알고리즘으로 구현한다고 생각하고 모든 경우의 수의 작동 순서를 생각해보자.
배열은 [ 1, 2, ... , 9 ] 이다.
1. 먼저, Key 0 ~ 8의 중간값인 Key=4와 비교한다.
Arr[4]의 값은 5다.
만약 찾는 값이 5라면? return key;
만약 찾는 값이 <5라면? 그 값이 Key=4보다 왼쪽에 있음이 자명하므로, 다음 탐색 구간은 Key 0 ~ 3이다.
만약 찾는 값이 <5라면? 그 값이 Key=4보다 오른쪽에 있음이 자명하므로, 다음 탐색 구간은 Key 5 ~ 8이다.
1-L) Key 0 ~ 3의 중간값은 1.5이므로, Key=1과 비교한다.
Arr[1]의 값은 2다.
만약 찾는 값이 2라면? return key;
만약 찾는 값이 <2라면? 그 값이 Key=1보다 왼쪽에 있음이 자명하므로, 다음 탐색 구간은 Key 0 ~ 0 이다.
만약 찾는 값이 >2라면? 그 값이 Key=1보다 오른쪽에 있음이 자명하므로, 다음 탐색 구간은 Key 2 ~ 3 이다.
1-L-L) Key 0 ~ 0 의 중간 값은 0이므로, Key=0과 비교한다.
Arr[0]의 값은 1이다.
만약 찾는 값이 1이라면? return key;
이외의 경우는 존재하지 않는다.
1-L-R) Key 2 ~ 3 의 중간 값은 2.5이므로, Key=2와 비교한다.
Arr[2]의 값은 3이다.
만약 찾는 값이 3이라면? return key;
만약 찾는 값이 >3이라면? 그 값이 Key=2보다 오른쪽에 있음이 자명하므로, 다음 탐색 구간은 Key 3 ~ 3 이다.
왼쪽에 있는 경우는 없다.
1-L-R-R) Key 3 ~ 3 의 중간 값은 3이므로, Key=3과 비교한다.
Arr[3]의 값은 4이다.
만약 찾는 값이 4라면? return key;
이외의 경우는 존재하지 않는다.
간단하게 중간값을 포함한 왼쪽 수 1~5를 탐색할 때의 경우의 수를 모두 적어봤다.
이 과정에서 계속 반복된 Arr[key]의 값을 찾는 값(Find)와 비교하는 과정을 코드로 작성해보면 이렇다.
int left, right;
int key = (left + right) / 2;
if(arr[key] == find) { // 찾는 수가 key에 있다면 반환
return key;
}
if(find > arr[key]) { // 찾는 수가 배열의 수보다 크면, 오른쪽에 있음. -> 왼쪽 범위를 줄임
left = key+1;
}
if(find < arr[key]) { // 찾는 수가 배열의 수보다 작으면, 왼쪽에 있음. -> 오른쪽 범위를 줄임
right = key-1;
}이제 left=0, right=arr.length-1 일 때 이 과정을 반복하기만 하면 된다.
반복문을 사용하려면 반복을 종료하는 조건이 필요한데, 이것은 배열에 찾으려는 값이 없을 때 필요하므로 생각해보자.
위에서 쭉 적어봤던 이진 탐색의 흐름을 생각해보면, Find값을 찾아 left와 right의 범위가 점점 줄어든다.
계속 찾지 못하면 결국 left와 right가 같아지는 시점이 오는데, ( 위의 1-L-L이나 1-L-R-R 같은 경우 )
이 때도 발견하지 못하면 'left = right = key'인 상황에서 'left = key+1', 'right = key-1' 중에 하나가 실행된다.
어느 쪽이 실행되던 그 결과는 left = right + 1이고, 이 경우 탐색 범위는 -1이므로 탐색할 수 없다.
그러므로 반복문의 조건은 left가 right보다 작거나 같을 때로 한다면, 모든 경우의 수를 탐색할 수 있을 것이다.
그리고, 값을 찾지 못한 경우에는 반복문 바깥에서 -1을 반환한다.
이를 코드로 정리해보면 다음과 같다.
int[] array = new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9}
int left = 0;
int right = array.length-1;
for(int key = (left+right)/2 ; left <= right ; key = (left+right)/2) {
if(find == array[key]) { // 같은 경우
return key;
} else if (find > array[key]) { // 찾으려는 값이 큰 경우
left = key + 1;
} else if (find < array[key]) { // 찾으려는 값이 작은 경우
right = key - 1;
}
}
return -1;
자, 그러면 기본적인 이진 탐색에 대해서는 알아봤으니까....
좀 더 머리를 아프게 만들 이진 탐색에 대해서 추가로 알아보자.
배열에 중복된 값이 있고, 그 중복된 값 중에서 가장 왼쪽 혹은 가장 오른쪽의 값을 반환하는 방법이다.
자 심플한 '중복이 있는 배열'을 가져와봤다.
우리는 여기서 5를 찾아야 하는데, 가장 왼쪽에 있는 5의 Key와 가장 오른쪽의 5의 Key를 찾아보자.
먼저 왼쪽 5를 찾는 방법이다.
기본적인 이진 탐색 순서에 따라서 arr[4] 와 5를 비교해보면, 같다.
그러나 우리는 arr[4]의 5가 가장 왼쪽에 있는 5인지 확신할 방법이 없다.
그렇다면 어떻게 해야 할까?
1. arr[4]부터 왼쪽으로 key를 1씩 줄여나가면서 5가 아닌 지점의 key+1이 가장 왼쪽이다.
가능한 방법이지만, 그러면 최악의 경우 O(N/2) 이므로, O(logN)시간을 지킬 수 없다.
그렇기 때문에 이진 탐색의 룰을 그대로 따르는 방법에 대해 생각해보자.
우리는 Find값을 찾았지만, 이 값이 '현재의 중앙보다 왼쪽'에 추가로 더 있는지 확인할 필요가 있다.
'왼쪽'이다.
기본 이진 탐색에서 우리가 왼쪽 값을 탐색하려면? right = key-1을 통해 탐색 범위를 중앙의 왼쪽으로 좁혀줬었다.
여기서도 똑같은 방법으로 해보자.
그러면 조건문은 다음과 같다.
Find > arr[key] : left = key+1 // 찾는 값이 중앙값보다 크므로 오른쪽으로 범위를 좁힌다.
Find <= arr[key] : right = key-1 // 찾는 값이 왼쪽에 있거나 탐색해야하므로 왼쪽으로 범위를 좁힌다.이 방식을 따라서 한 번 계산을 손으로 진행해보자.
1. 먼저, arr[4]에서 왼쪽으로 범위를 좁혔으니 다음 범위는 0~3이고, 중앙 값은 1이다.
Find = 5 > arr[1] = 3 이므로, left = key + 1 = 2이다.
2. 범위는 2 ~ 3 이고, 중앙 값은 2이다.
Find = 5 > arr[2] = 3 이므로, left = key + 1 = 3 이다.
3. 범위는 3 ~ 3 이고, 중앙 값은 3이다.
Find = 5 == arr[3] = 5 이므로, right = key - 1 = 2 이다.
4. 범위는 3 ~ 2 이므로 반복이 종료된다.
가장 마지막에 탐색한 값인 left가 가장 왼쪽 값이 됬다.
그러므로, 반복이 종료된 후 return left;를 하면 가장 왼쪽의 5를 반환할 수 있을 것이다.
예외 검사를 위해 하나 더 가정을 해보자.
배열에서 참고했던 첫 중앙 값이 가장 왼쪽 값인 경우다.
이 배열에 대해 위에서 새로 구한 가장 왼쪽 값의 key를 구하는 이진 탐색을 진행해보자.
1. 범위는 0 ~ 6, 중앙 값은 3
Find = 5 == key[3] = 5 이므로, right = key - 1 = 2 이다.
2. 범위는 0 ~ 2, 중앙 값은 1
Find = 5 > key[1] = 3 이므로, left = key + 1 = 2 이다.
3. 범위는 2 ~ 2, 중앙 값은 2
Find = 5 > key[2] = 3 이므로, left = key + 1 = 3 이다.
4. 범위는 3 ~ 2, 반복문이 종료된다.
이 경우도 left 값이 key = 3으로 올바른 값을 반환한 것을 볼 수 있다.
그렇다면 이를 바탕으로 가장 왼쪽 값의 Key를 구하는 이진 탐색 코드를 작성해보면
int[] arr = // 숫자 배열
int left = 0;
int right = arr.length - 1;
for(int key = (left+right) / 2 ; left <= right ; key = (left+right) / 2) {
if(find > arr[key]) left = key+1;
else right = key-1;
}
return left;이 된다.
이 방식이 증명됬으므로, 사실 오른쪽 값의 Key를 구하는 방법도 쉽게 구할 수 있다.
우리가 처음에 왼쪽 Key를 구하기 위한 방법에 대해 접근할 때 했듯이, 오른쪽 Key에 대해서도 똑같이 하면된다.
find == arr[key] 일 때 left = key + 1을 하면, right값이 오른쪽 key가 될 것이다.
위의 코드를 참조하면 다음과 같다.
if(find >= arr[key]) left = key+1;
else right = key-1;좀 더 역할이 반전됬음을 직관적으로 표현하면
if(find < arr[key]) right = key-1;
else left = key+1;이다.
이 방식이 실제로 가장 오른쪽 key값을 구할 수 있는지 방금 테스트 했던 배열로 검사해보자.
1. 범위는 0 ~ 6, 중앙 값은 3
Find = 5 == arr[3] = 5 이므로, left = key + 1 = 4
2. 범위는 4 ~ 6, 중앙 값은 5
Find = 5 < arr[5] = 7 이므로, right = key - 1 = 4
3. 범위는 4 ~ 4, 중앙 값은 4
Find = 5 == arr[4] = 5 이므로, left = key + 1 = 5
4. 범위는 5 ~ 4 반복문이 종료된다.
종료시 변수 상태 : left = 5, right = 4
이를 통해, 왼쪽 값을 구할 때의 내용을 완전히 반전시키면 오른쪽 값을 구하는 내용으로 쓸 수 있다는 사실을 알았다.
확실히 과정을 따라가면서 글로 정리를 하니, 기존보다 좀 더 이해가 잘 되는 느낌이다.
그래도 이 값이 오른쪽에 있으니 왼쪽 범위를 오른쪽으로 좁혀서..
막 이렇게 왔다갔다 해버리니까 좀 어지럽다. 이과할걸...!
백준에서 이진 탐색에 대한 도전 카테고리가 있다. https://www.acmicpc.net/step/29
위에 적어둔 링크에 들어가면 풀 수 있는데, 5단계 까지는 순수 이진 탐색으로 푸는 문제이므로 개념 공부를 위해 풀어보면 좋을 것 같다. 6단계부터는 이진 탐색은 이진 탐색인데.... 이걸 아니라고 하기도 뭐하고... 뭐 이런 느낌이라 개념 공부중이라면 비추