[Kotlin] 이진 탐색 (Binary Search)

개념

탐색 범위를 줄여나가며 특정 값을 찾아내는 알고리즘이다.
리스트가 정렬이 되어있어야만 한다는 단점이 있기는 하지만 순차 탐색에 비해 탐색 시간이 굉장히 빠르다.

업다운 게임을 해봤으면 알겠지만, 중간값을 외친 후 업다운을 듣고 또 그의 중간 값을 외치고 정해진 값을 찾는 것이 효율적이다.
이처럼 이진 탐색도 중간 값을 찾고 '다운'이라면 중간 값 기준으로 왼쪽(작은 쪽)에서의 중간 값을 찾으며 범위를 좁혀가고, '업'이라면 오른쪽(큰 쪽)으로 중간 값을 찾으며 범위를 점차 좁혀 원하는 값을 찾는다.

시간복잡도

순차 탐색 : O(n)
이진 탐색 : O(logn)

코드

 fun binarySearch(nums: IntArray, target: Int): Int {
    val answer = -1

    var low = 0
    var high = nums.lastIndex

    while (low <= high) {
        val mid = (low + high) / 2

        if (nums[mid] < target) {
            low = mid + 1
        } else if (nums[mid] > target) {
            high = mid - 1
        } else {
            return mid
        }
    }

    return answer
}

관련 문제

1. 수 찾기
2. 숫자 카드
3. 숫자 카드2
4. 랜선 자르기
5. 나무 자르기