Daily LeetCode Challenge - 35. Search Insert Position

Problem From.

https://leetcode.com/problems/single-element-in-a-sorted-array/

오늘 문제는 같은 숫자가 2개씩 반복되는 오름차순 array 에서 반복되지 않는 숫자 하나를 찾는 문제였다.

Binary Search 를 통해서 풀 수 있으며, 앞에서부터 항상 2개씩 짝을 맞춘 숫자가 반복되므로, mid 값을 구했을때, 그 값이 짝수이면 그 다음수와 같아야하고, 그 값이 홀수이면 그 전 수와 같이 같아야한다.

만약 그렇지 않다면 mid 의 앞부분에 짝이 맞지 않는 수가 들어있다는 말이고, 아니라면 mid 의 뒷부분에 짝이 맞지 않는 수가 들어있다는 말이 된다.

위에 언급한 내용을 코드로 풀어내면 아래와 같다.

class Solution {
    fun singleNonDuplicate(nums: IntArray): Int {
        
        return binarySearch(nums, 0, nums.lastIndex)
        
    }
    
    private fun binarySearch(nums: IntArray, start: Int, end: Int): Int {
        
        var mid = (start + end) / 2
        
        if((start + 1) > (end - 1)) return nums[mid]
        
        if(mid % 2 == 1) mid -= 1
        
        if(nums[mid] == nums[mid + 1]) {
            return binarySearch(nums, start + 2, end)
        }else {
            return binarySearch(nums, start, end - 2)
        }
        
    }
}

이 풀이의 시간 복잡도는 O(logN) 이 된다.