35 - 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)。

思路

實作二元搜尋法當 target 存在於陣列

# nums = [1, 3, 5, 6], target = 5

left = 0, right = len(nums) - 1

while left <= right:
    mid = (left + right) // 2
                                                #                           l  m     r
                                                # First pass: [1, 3, 5, 6]
    if nums[mid] == target:
        return mid
    elif nums[mid] > target: 
        right = mid - 1     
    else:
        left = mid + 1      # target 大於 mid 所指的元素
                                              #                                 l  r
                                              # First pass: [1, 3, 5, 6]
        
                                                # ...
                                                #                    lm  r
                                                # Second pass: [1, 3, 5, 6]
                                                # nums[mid] = target, return mid
return mid

當 target 不存在於陣列

# target 不存在於陣列
# nums = [1, 3, 5, 6], target = 0

left = 0, right = len(nums) - 1

while left <= right:
    mid = (left + right) // 2
                                                #                           l  m     r
                                                # First pass: [1, 3, 5, 6]
    if nums[mid] == target:
        return mid
    elif nums[mid] > target: 
        right = mid - 1     # target 小於 mid 所指的元素
                                              #                          lr  
                                              # First pass: [1, 3, 5, 6]
        
                                                #               lr
                                                # Second pass: [1, 3, 5, 6]
                                                # nums[mid] = target, return mid
                                                
                                                # target 小於 mid 所指的元素
                                                #            r  l
                                                # Second pass: [1, 3, 5, 6]
    else:
        left = mid + 1

return left             # left > right, exit while loop, return left

完整程式碼

function searchInsert(nums: number[], target: number): number {
    let l = 0, r = nums.length - 1
    
    while (l <= r) {
        const mid = Math.floor((l + r) / 2)
        if (nums[mid] == target) {
            return mid
        } else if (nums[mid] > target) {
            r = mid -1
        } else {
            l = mid + 1
        }
    }
    
    return l
};