排序陣列中找出插入位置

目標數值應該介於或者等於相鄰數值:

nums[i-1] < target && target <= nums[i]

依據這個概念我們可以寫出基本款 O(n):

因為排序,我們可以利用二元來搜尋位置。

偷懶用內建的 binarySearch O(logn):

Arrays.binarySearch 手冊寫出沒有找到相符數值,會回傳負數最接近的位置,此題是插入,所以要 -(i + 1)

讓我們乖乖寫自己的版本吧,一如往常寫個遞迴的版本 O(logn):

核心虛擬碼:

searchInsert = if nums[mid] == target:
return mid
elif target <= nums[mid]:
return searchInsert(nums, target, i, n/2)
else:
return searchInsert(nums, target, mid, n - n/2)

延伸問題:排序陣列有重複的數值?