原題

給定一個排序數(shù)組和一個目標(biāo)值，如果在數(shù)組中找到目標(biāo)值則返回索引。如果沒有，返回到它將會被按順序插入的位置。

[1,3,5,6]，5 → 2
[1,3,5,6]，2 → 1
[1,3,5,6]， 7 → 4
[1,3,5,6]，0 → 0

解題思路

• 對于插入排序，所有數(shù)字都要插入一次，而且對于數(shù)組，要整體向后移動，所以這時的插入即從后往前交換到不能交換位置。二分查找再插入并不會加快速度
• 本題是假設(shè)有一個很大的數(shù)組，數(shù)組之間可能留有空隙，只需要插入一個或幾個數(shù)字，所以需要二分法快速定位
• 概念偷換可以減少if/else判斷語句！??！本題把target存在和不存在結(jié)合在一起 => 找到數(shù)組中有幾個數(shù)比target小
• 核心部分都寫成start = mid或者end = mid，具體情況最后討論

完整代碼

class Solution:
    """
    @param A : a list of integers
    @param target : an integer to be inserted
    @return : an integer
    """
    def searchInsert(self, A, target):
        if not A:
            return 0
            
        if target < A[0]:
            return 0
            
        start, end = 0, len(A) - 1
        while start + 1 < end:
            mid = start + (end - start) / 2
            if A[mid] == target:
                return mid
            elif A[mid] < target:
                start = mid
            else:
                end = mid
                
        if A[end] == target:
            return end
        elif A[end] < target:
            return end + 1
        elif A[start] == target:
            return start
        else:
            return end