이진 탐색
영어로는 binarySearch라고 한다. 이 알고리즘은 데이터가 정렬되어 있는 배열에서 특정한 값을 찾아내는 알고리즘이다. 여기서 핵심이 되는 말은 "정렬"이다. 이진 탐색이 이뤄지기 위한 조건이 바로 저 정렬되어 있다는 것이다.
이진 탐색 방식
알고리즘의 방식은 다음과 같다. 우선 정렬되어 있는 데이터 배열이 있다. 일단 오름차순이라고 가정하자. 우리의 목표는 값 k를 찾는 것이다. 이 이진 탐색 방식을 아래 순서로 설명한다.
- 배열에서 중앙에 위치하는 임의의 값을 확인하고 k와 비교한다.
- 값이 k보다 작다면 k는 해당 값보다 배열의 index 상 우측에 존재한다. 따라서 k 다음 값부터 마지막까지의 배열에 1번을 반복한다. 값이 k보다 크다면 반대로 k보다 작은 값들의 배열로 1번을 반복한다.
- 이렇게 탐색을 하다 k 값을 찾게 되면 종료한다.
- 혹은 전체를 탐색했지만 k 값을 찾지 못하고 다음 수색해야 하는 배열이 비어있다면, 해당 값이 존재하지 않는다고 판단하고 종료한다.
단순에 보이는 이 방식은 기존에 O(N)이 걸렸던 방식을 O(logN)까지 줄여준다.
코드로의 구현
이진 탐색을 kotlin 코드로 구현하면 아래와 같다. start가 end보다 커지거나, k를 발견할 경우 멈추게 되어 있다. k를 찾지 못하고 start > end가 되면 -1을 return하고 이는 값이 존재하지 않음을 의미한다.
fun binarySearch(arr: IntArray, k:Int): Int {
var start = 0
var end = arr.lastIndex
while (start <= end) {
val mid = (start+end)/2
val cur = arr[mid]
if (cur < k) {
start = mid + 1
} else if (cur == k) {
return mid
} else {
end = mid - 1
}
}
return -1
}이진 탐색 알고리즘의 변형
이진 탐색 알고리즘의 경우 중복되지 않은 값들 중에서 특정한 값을 찾아낼 때 유용하다. 그렇다면 중복되는 값들이 배열로 주어졌을 때는 어떻게 해야할까? 이떄 유용하게 사용할 수 있는 변형된 형태의 이진 탐색 알고리즘이 있다. 바로 lower bound와 upper bound이다.
참고자료 : https://jackpot53.tistory.com/33
lower bound
말 그대로 아래쪽 경계를 의미한다. 중복이 허용되는 배열에서 특정한 값 k를 찾을 때 해당 k 값이 여러개 존재할 수 있다. lower bound의 경우 그러한 k 값들 중 가장 먼저 등장하는 k 값을 찾아준다. 또, 이러한 특징 때문에 k값 보다 크거나 같은 값이 처음으로 등장하는 위치를 찾아주는 역할도 한다.
구현은 아래와 같다.
fun lowerBound(arr:IntArray, k:Int): Int {
var start = 0
var end = arr.lastIndex
while (start < end) {
val mid = (start+end)/2
val cur = arr[mid]
if (cur < k) {
start = mid + 1
} else {
end = mid
}
}
return start
}
upper bound
lower bound와 정 반대로 k값보다 처음으로 큰 값이 나오는 원소를 찾아준다.
구현은 아래와 같다.
fun upperBound(arr:IntArray, k:Int):Int {
var start = 0
var end = arr.lastIndex
while (start < end) {
val mid = (start+end)/2
val cur = arr[mid]
if (cur <= k) {
start = mid + 1
} else {
end = mid
}
}
return end
}
lower & upper bound의 활용
위에서도 언급했지만 lower bound의 경우 k값보다 크거나 같은 값이 처음으로 등장하는 지점을 찾기 위해서, upper bound의 경우 k값보다 큰 값이 처음으로 등장하는 지점을 찾기 위해서 사용한다. 해당 개념을 머리속에 잘 담아 두고 상황에 맞게 활용하면 된다.
이진 탐색의 활용
이진 탐색 자체를 탐색에 사용할 수 도 있지만, 고약한 문제의 경우 모든 경우의 수를 빠르고 효율적을 탐색할 수 있는 방법이 될 수도 있다. 예를 들어 1~n까지의 값들 중 답이 되는 값 k를 찾는 경우 말이다. 이럴 때는 문제에 이진 탐색이라는 것이 들어나지는 않으나, 생각치도 못하게 이진 탐색이 해법이여 버리는 상황들이 있다.
아래 문제가 그 예시이다. 나도 해설을 찾아 보기 전까지는 감도 찾지 못했었다. 그러나 사실 그렇게 좋은 문제라고 생각하지는 않는다.(개인의 생각이다.)
입국 심사 문제
