題目：

給定一個排序數組和一個目標值，在數組中找到目標值，并返回其索引。如果目標值不存在于數組中，返回它將會被按順序插入的位置

---

方法一：二分查找

假設題意是在排序數組中尋找是否存在一個目標值，則可以利用二分法在Ologn的時間內找到是否存在目標值，但這題還有個額外條件，即如果不存在數組中的時候需要返回按順序插入的位置。需要對二分法做些修改

考慮這個插入的位置pos,它成立的條件為：

nums[pos-1]<target<=nums[pos]

其中nums代表排序數組，由于如果存在這個目標值，返回的索引也是pos,即可以將兩個條件合并后并得出最后的目標：在一個有序數組中找到第一個大于等于target的下標

問題轉化到這個，直接套用二分法即可，即不斷用二分法逼近查找第一個大于等于target的下標，ans初始設置為數組長度可以省略邊界條件的判斷，因為存在一種情況是target大于數組中的所有數，此時需要插入到數組長度的位置。

class Solution(object):def searchInsert(self, nums, target):""":type nums: List[int]:type target: int:rtype: int"""left=0  #指向數組的起始位置(索引0)right=len(nums)-1  #指向數組的末尾位置(最后一個元素的索引)while left<=right:  #左指針不大于右指針。這保證了搜索區間始終有效middle=(left+right)//2 #計算中間位置的索引if nums[middle]<target: #如果中間元素小于目標值，說明目標值應該在右半部分left=middle+1 #將左指針移動到中間位置右側elif nums[middle]>target: #如果中間元素大于目標值，說明目標值應該在左半部分right=middle-1  #將右指針移動到中間位置左側else:return middlereturn right+1  #循環結束還沒找到目標值,right+1就是它應該插入的位置1

時間復雜度:O(logn)其中n為數組的長度

空間復雜度:O(1)

源自力扣官方題解