[Algorithm] Binary Search (이진검색)

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

Binary Search의 기본 조건 : 오름차순 정렬

 

A1. indexOf 이용 (248 ms, 39.5MB)

class Solution {
    fun search(nums: IntArray, target: Int): Int {
        return nums.indexOf(target)
    }
}

 

A2. binarySearch 구현 (232ms, 38MB)

class Solution {
    fun search(nums: IntArray, target: Int): Int {
        var left = 0
        var right = nums.size - 1
        var result = -1

        while (left <= right) {
            val pivot = left + (right - left) / 2
            if (nums[pivot] == target) {
                result = pivot
                break
            }

            if(nums[pivot] < target) {
                left = pivot + 1
            } else {
                right = pivot - 1
            }
        }

        return result
    }
}

 

 Binary Search란 순차적으로 요소를 찾는 순차 탐색이 아니라, 탐색해야 하는 range의 중간부터 반복적으로 찾는 방법입니다. 아래 코드에서 pivot이 중간 값을 지칭하는 index이고, left, right가 가리키는 값과 비교하면서 요소를 탐색합니다.

 

A3. binarySearch 이용 (599ms, 68MB)

class Solution {
    fun search(nums: IntArray, target: Int): Int {
        val pivot = nums.binarySearch(target, 0, nums.size)
        return if (pivot >= 0) pivot else -1 
    }
}

 

 참고로 Kotlin에서 제공하는 binarySearch함수는 리턴이 insertion point를 나타냅니다. 만약 어떤 요소를 찾은 결과가 -3이라면, 역으로 -(-3 + 1) 즉 2번째 index에 해당 요소가 추가되면 된다는 뜻입니다.

Return the index of the element, if it is contained in the list within the specified range; otherwise, the inverted insertion point (-insertion point - 1)