題目:

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.

給定一個sorted list跟目標值(target),若target在list內則返回該值的index,若無則返回target放入後陣列還維持sorted list的index值

整個題目二分搜的味道都很重了,題目還將複雜度限制在O(logn),不用二分搜都難

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

在開始前先處理一些能迅速判斷的特例:
(1)target小於第一項那就會insert到第一項的位置,等於第一項就回傳第一項的index,兩種狀況都是回傳0
(2)target等於最後一項就回傳最後一項的index(len(list)-1)
(3)target大於最後一項會insert到最後一項後,回傳最後一項的index+1(len(list))
接著就開始二分,設左值(l)和右值(r),計算左右的中間值(mid),大於mid下限(l)拉高至mid,小於mid上限(r)拉低至mid
一旦偵測到mid和target相等就回傳,但若target不在list內,最後l,r會相鄰,此時target該插入的index便是r(插入後list仍是sorted list)
最後執行時間47ms(faster than 97.22%)

那我們下題見