[LeetCode / Kotlin] Search Insert Position

문제

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 <= 104
• -104 <= nums[i] <= 104
• nums contains distinct values sorted in ascending order.
• -104 <= target <= 104
  
  

 

나의 풀이

 

O(logn) 의 시간복잡도로 문제를 풀라고 나와있어서, 이진탐색일것이라고 감이 왔다.

 

1. 범위내의 중간값 선정

2. 중간값을 기준으로 대소비교를하여 범위를 조정한다.

class Solution {
    fun searchInsert(nums: IntArray, target: Int): Int {
        var start = 0
        var end = nums.lastIndex
        

        while(start <= end) {
            var mid = start + ((end - start) / 2 )

            if (nums[mid] == target) {
                return mid
            } else if (nums[mid] > target) {
                end = mid - 1
            } else {
                start = mid + 1
            }
        }

        return start
    }
}