0035. Search Insert Position - chasel2361/leetcode GitHub Wiki

Given a sorted array 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 may assume no duplicates in the array.

Example 1:
Input: [1,3,5,6], 5
Output: 2

Example 2:
Input: [1,3,5,6], 2
Output: 1

Example 3:
Input: [1,3,5,6], 7
Output: 4

Example 4:
Input: [1,3,5,6], 0
Output: 0

這題應該算是最基本的 binary search ，雖然可以一項一項搜尋，但速度太慢了，所以我先取中間的 index 來比較，如果取出來的數比目標小，那就再取右半邊的中間位置，若取出的數比目標大，則取左半邊中間，以此類推

我使用三個變數來當作參考， l 表示待取範圍的最左邊、 r 表示待舉範圍的最右邊， n 表示待取範圍的中間，根據不同條件更改 l 以及 r 值，最後即可找到插入數值的位置

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        l = 0
        r = len(nums)
        while True:
            n = (l + r)//2
            if target > nums[n]:
                if (n == len(nums) - 1):
                    return n + 1
                elif (target < nums[n + 1] and n < len(nums)-1):
                    return n + 1
                l = n
            else:
                if (n == 0):
                    return n
                elif target > nums[n - 1] and n > 0:
                    return n
                r = n

參考其他大大的做法之後發現我的寫法判斷式有點太多，可以簡化成下面這樣

[1] 把 l 以及 r 多移動一格的原因是為了把 n 所代表的數也剔除於篩選範圍，更加縮小搜尋範圍。如此一來答案就只會存在於兩個情況
[2] target == nums[n]， 此時答案為 n
[3] target 不存在於 nums 中，此時答案為 l

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        l = 0
        r = len(nums) - 1
        while l <= r:  
            n = (l + r)//2
            if target < nums[n]:
                r = n - 1  # [1]
            elif target > nums[n]:
                l = n + 1  # [1]
            else:
                return n  # [2]
        return l  # [3]

這樣寫的時間複雜度為 O(N)，空間複雜度為 O(1)