[Kotlin] Leetcode 35. Search Insert Position

Problem

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You must write an algorithm with O(log n) runtime complexity.

 

Example 1:

Input: nums = [1,3,5,6], target = 5
Output: 2

Example 2:

Input: nums = [1,3,5,6], target = 2
Output: 1

Example 3:

Input: nums = [1,3,5,6], target = 7
Output: 4

 

Constraints:

• 1 <= nums.length <= 10^4
• -10^4 <= nums[i] <= 10^4
• nums contains distinct values sorted in ascending order.

Ascending으로 정렬된 배열이면 그냥 binary search를 사용하면 O(log N)에 찾을 수 있다는 것을 지난 시간에 배웠습니다. 기억이 안나시는 분은 아래 링크를 참고하세요!

[Kotlin] Leetcode 704. Binary Search

 

class Solution {
    fun searchInsert(nums: IntArray, target: Int): Int {
        var startN = 0
        var endN = nums.size
        while(startN < endN)
        {
            var midN = (startN + endN) / 2
            if( nums[midN] == target) return midN
            else if (nums[midN] > target) endN = midN
            else startN = midN + 1
        }
        return startN
    }
}

nums.length가 10^4이므로 Int형으로 처리가 충분히 가능합니다.

startN + endN을 그냥 하여도 문제가 없습니다.

 

target을 계속 찾아서 있으면 그 위치를 그냥 return하면 되고

target이 없다면 start와 end를 계속 업데이트 하여 start가 end와 같거나 클때까지 계속 탐색을 하고나서

startN을 return하면 바로 그 위치가 target값을 넣어야 하는 위치가 됩니다.

 

nums = [1,3,5,6]인 경우 7은 없기 때문에 endN은 4이되고 계속 nums[midN]보다 target이 클 것이기 때문에 startN은 midN + 1이 될 것입니다.

 

결국 마지막으로 (2+4)/2 = 3이 되고 거기에 +1을 하면 startN은 4가 됩니다. 

4의 위치는 아무것도 없는 index이고 이미 빠져나왔기 때문에 그 위치에 7을 넣으면 됩니다.

 

이렇게 start와 end를 잘 설정해주면 문제를 쉽게 풀 수 있습니다. 

binary search에서 start, end를 어떻게 설정하는지에 따라 값이 많이 달라집니다!