python搜索插入位置實(shí)例分析

【題目】

給定一個(gè)排序數(shù)組和一個(gè)目標(biāo)值，在數(shù)組中找到目標(biāo)值，并返回其索引。如果目標(biāo)值不存在于數(shù)組中，返回它將會(huì)被按順序插入的位置。

你可以假設(shè)數(shù)組中無(wú)重復(fù)元素。

示例 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、暴力解法：遍歷數(shù)組，查找元素。

2、二分查找：題目類型為找到第一個(gè)大于等于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
# 循環(huán)結(jié)束后，得到的結(jié)果是：nums[j] <= target < nums[i]
# 解釋：只要nums[mid]大于target，j就前移，因此最終nums[j]肯定小于等于target；同理，nums[i]大于target。
# 可以發(fā)現(xiàn)，最重要的是nums[mid] > target這個(gè)式子中的運(yùn)算符，以及返回的下標(biāo)，這兩個(gè)也是通用代碼中必須要根據(jù)題目進(jìn)行修改的部分。
# 當(dāng)nums[mid] > target，最終結(jié)果nums[j] <= target < nums[i]
# 當(dāng)nums[mid] >= target，最終結(jié)果nums[j] < target <= nums[i]

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

【代碼】

python版本

二分查找

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums) - 1
        
        # 第一個(gè) >= 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