思路简单，细节复杂！

二分查找

一、3种题型

1、查找目标值是否存在

• 69. x 的平方根 - 力扣（LeetCode）
• 35. 搜索插入位置 - 力扣（LeetCode）

使用二分查找指定目标值，只要找到目标值就立即返回其下标。

• 当右指针为最后一个元素的下标r = len(nums) - 1时，查找区间为闭区间[l, r]，只要在这个区间内的元素都应该被查找。

• 当l > r时没有元素可以再被查找，所以循环条件为l <= r。

• 为了防止数组长度过大，l + r溢出，使用mid = l + (r - l) // 2计算二分位置。

• target == nums[mid]，因为只要找到一个相同的元素即可，所以相等时立即返回mid。

• 当target不等于nums[mid]时，因为查找范围是闭区间[l, r]，所以缩小范围的时候，依然保持闭区间，

• • target < nums[mid]，移动右指针缩小查找范围，此时查找范围是[l, mid-1]
  • target > nums[mid]，移动左指针缩小查找范围，此时查找范围是[mid+1, r]

• 最后一次查找是当l = r时，如果这次还没有查找到，即查找失败，return -1

class Solution:
    def searchElement(self, nums: List[int], target: int) -> int:
        if not nums: return -1
        l, r = 0, len(nums) - 1
        while l <= r:
            mid = l + (r - l) // 2
            if target == nums[mid]:
                return mid
            if target < nums[mid]:
                r = mid - 1
            else:
                l = mid + 1
        return -1

• 左闭右闭，[left, right]
• 循环条件，left <= right
• 指针移动，left = mid + 1; right = mid -1

2、查找目标值左边界

• 278. 第一个错误的版本 - 力扣（LeetCode）

查找目标值的左边界，找到 target时不要立即返回，而是缩小搜索区间的右指针 r，在左闭右开区间 [l, mid) 中继续搜索，即不断向左收缩，达到锁定左边界的目的。

• 当右指针为数组长度r = len(nums)，即最后一个元素下标加一时，查找范围是[l, r)。

• 当l = r时没有元素可以再被查找，所以循环条件为l < r。

• 为了防止数组长度过大，l + r溢出，使用mid = l + (r - l) // 2计算二分位置。

• target == nums[mid]，因为要找到目标元素的左边界，所以相等时不返回mid，而是以mid为右指针缩小查找区间，因为查找范围是左闭右开区间[l, r)，所以缩小范围的时候，依然保持左开右闭区间，为[l, mid)。

• 当target不等于nums[mid]时

• • target < nums[mid]，缩小查找范围右边界，此时查找范围是[l, mid)
  • target > nums[mid]，缩小查找范围左边界，此时查找范围是[mid+1, r)

• 最后一次查找是当l = r-1时，这次循环完成后l = r，此时标志循环结束

• • 如果l = len(nums)，说明目标值大于数组中所有元素，查找失败，return -1；
  • 如果nums[l] != target，说明数组中没有这个值，查找失败，return -1
  • 如果非上述两种情况，这时l = r，返回l或者r即为target左边界。

class Solution:
    def searchLeftBorder(self, nums: List[int], target: int) -> int:
        if not nums: 
            return -1
        l, r = 0, len(nums)
        while l < r:
            mid = l + (r - l) // 2
            if target == nums[mid]:
                r = mid
            if target < nums[mid]:
                r = mid
            else:
                l = mid + 1
        return l

• 左闭右开，[left, right)
• 循环条件，left < right
• 下标移动，left = mid + 1; right = mid
• mid与target相等时，区间继续向左移动，R = mid

3、查找右边界

• 34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

找到 target时不要立即返回，而是缩小搜索区间的左指针 l，在区间 [mid+1, r) 中继续搜索，即不断向右收缩，达到锁定右边界的目的。

• 当右指针为数组长度r = len(nums)，即最后一个元素下标加一时，查找范围是[l, r)。

• 当l = r时没有元素可以再被查找，所以循环条件为l < r。

• 为了防止数组长度过大，l + r溢出，使用mid = l + (r - l) // 2计算二分位置。

• target == nums[mid]，因为要找到目标元素的右边界，所以相等时不返回mid，而是以mid+1为左指针缩小查找区间，因为查找范围是左闭右开区间[l, r)，所以缩小范围的时候，依然保持左开右闭区间，为[mid+1, r)。

• 当target不等于nums[mid]时

• • target < nums[mid]，缩小查找范围右边界，此时查找范围是[l, mid)
  • target > nums[mid]，缩小查找范围左边界，此时查找范围是[mid+1, r)

• 最后一次查找是当l = r - 1时，这次循环完成后l = r，此时标志循环结束

• • 如果r = 0，说明目标值小于数组中所有元素，查找失败，return -1；
  • 如果nums[l-1] != target，说明数组中没有这个值，查找失败，return -1
  • 如果非上述两种情况，因为在target = nums[mid]的时候执行的是l = mid + 1，又因此时l = r所以返回l - 1或者r - 1即为target右边界。

class Solution:
    def searchRightBorder(self, nums: List[int], target: int) -> int:
        if not nums: 
            return -1
        l, r = 0, len(nums)
        while l < r:
            mid = l + (r - l) // 2
            if target == nums[mid]:
                l = mid + 1
            if target > nums[mid]:
                l = mid + 1
            else:
                r = mid
        return l - 1

• 左闭右开，[left, right)
• 循环条件，left < right
• 下标移动，left = mid + 1; right = mid
• mid与target相等时，区间继续向右移动，L = mid + 1

二、参考教程

关于二分查找的细节 - 知乎 (zhihu.com)