【題目】

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

你可以假設數組中無重復元素。

示例 1:
輸入: [1,3,5,6], 5
輸出: 2
    
示例 2:
輸入: [1,3,5,6], 2
輸出: 1
    
示例 3:
輸入: [1,3,5,6], 7
輸出: 4
    
示例 4:
輸入: [1,3,5,6], 0
輸出: 0

【思路】

1、暴力解法：遍歷數組，查找元素。

2、二分查找：題目類型為找到第一個大于等于target的元素，返回其位置。

二分查找一般使用通用代碼：

i, j = 0, len(nums) - 1
while i <= j:
 mid = (i + j) // 2
 if nums[mid] > target:
  j = mid - 1
 else:
  i = mid + 1
return i
# 循環結束后，得到的結果是：nums[j] <= target < nums[i]
# 解釋：只要nums[mid]大于target，j就前移，因此最終nums[j]肯定小于等于target；同理，nums[i]大于target。
# 可以發現，最重要的是nums[mid] > target這個式子中的運算符，以及返回的下標，這兩個也是通用代碼中必須要根據題目進行修改的部分。
# 當nums[mid] > target，最終結果nums[j] <= target < nums[i]
# 當nums[mid] >= target，最終結果nums[j] < target <= nums[i]

怎么使用呢？1）根據題目，找到自己想要的循環后的結果；比如，找到第一個大于target的元素，結果就應該是num[j] <= target < nums[i]。2）寫入模板，根據需要更改運算符及返回值；比如，找到第一個大于target的元素，運算符應該是>，返回的是i。

【代碼】

python版本

二分查找

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums) - 1
        
        # 第一個 >= target的元素
        # nums[r] < target <= nums[l]
        while l <= r:
            mid = (l + r) // 2
            if nums[mid] >= target:
                r = mid - 1
            else:
                l = mid + 1
        
        return l