Skip to main content

1、二分搜索个人总结

Y-aong...About 9 min算法笔记左右指针双指针

1、二分搜索个人总结

一、二分查找定义

二分查找的基本思想是很简单的可能很多小学生都可以思考出来，但是实际去 写又会遇到很多问题。因为里面有很多细节需要注意。一不小心就会写失败。

二分查找的基本算法思想为：通过确定目标元素所在的区间范围，反复将查找范围减半，直到找到元素或找不到该元素为止。

二、二分查找的算法步骤

  1. 初始化：首先，确定要查找的有序数据集合。可以是一个数组或列表，确保其中的元素按照升序或者降序排列。
  2. 确定查找范围：将整个有序数组集合的查找范围确定为整个数组范围区间，即左边界 left 和右边界 right。
  3. 计算中间元素：根据 mid=⌊(left+right)/2⌋ 计算出中间元素下标位置 mid。
  4. 比较中间元素：将目标元素target 与中间元素 nums[mid]进行比较：
    • target == nums[mid]找到目标索引
    • target < nums[mid]目标位置在[left, mid-1], right=mid-1
    • target > nums[mid]目标位置在[mid+1, right],left=mid+1

我们可以使用一个简单的例子来说明

704. 二分查找open in new window

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

提示：

  1. 你可以假设 nums 中的所有元素是不重复的。
  2. n 将在 [1, 10000]之间。
  3. nums 的每个元素都将在 [-9999, 9999]之间。
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        
        # 在区间 [left, right] 内查找 target
        while left <= right:
            # 取区间中间节点
            mid = (left + right) // 2
            # 如果找到目标值，则直接返回中心位置
            if nums[mid] == target:
                return mid
            # 如果 nums[mid] 小于目标值，则在 [mid + 1, right] 中继续搜索
            elif nums[mid] < target:
                left = mid + 1
            # 如果 nums[mid] 大于目标值，则在 [left, mid - 1] 中继续搜索
            else:
                right = mid - 1
        # 未搜索到元素，返回 -1
        return -1

三、二分查找中的注意点

关于二分查找思路是非常简单的，但是实际写代码可能是非常容易写失败的，因为其中有很多的注意点

  • 区间的开闭问题，开区间、闭区间，左开右闭，左闭右开

  • mid的取值问题，mid = (left+ right) // 2, mid = (left+right+1) // 2

  • 出界条件的判断,while left < right, while left <= right

  • 搜索区间范围的选择，left = mid + 1, left = mid, right=mid-1，right= mid

3.1、区间的开闭问题

关于二分查找算法的左闭右闭区间、左闭右开区间都是可以实现的，但是一般来说左闭右开区间这种写法在解决问题的过程中，会使得问题变得复杂，需要考虑的情况更多，所以不建议使用左闭右开区间这种写法，而是建议：全部使用「左闭右闭区间」这种写法。

3.2、mid的取值问题

  1. mid = (left + right) // 2。
  2. mid = (left + right + 1) // 2 。

式子中 // 所代表的含义是「中间数向下取整」。当待查找区间中的元素个数为奇数个，使用这两种取值公式都能取到中间元素的下标位置。

除了上面提到的这两种写法，我们还经常能看到下面两个公式：

  1. mid = left + (right - left) // 2。
  2. mid = left + (right - left + 1) // 2。

这两个公式其实分别等同于之前两个公式，可以看做是之前两个公式的另一种写法。这种写法能够防止整型溢出问题（Python 语言中整型不会溢出，其他语言可能会有整型溢出问题）。

在 left+right的数据量不会超过整型变量最大值时，这两种写法都没有问题。在 left+right 的数据量可能会超过整型变量最大值时，最好使用第二种写法。所以，为了统一和简化二分查找算法的写法，建议统一写成第二种写法：

  1. mid = left + (right - left) // 2。

  2. mid = left + (right - left + 1) // 2。

3.3、出界条件的判断

二分查找算法的写法中，while 语句出界判断条件通常有两种：

  1. left <= right。
  2. left < right。

我们究竟应该使用哪一种写法呢？

  1. 如果判断语句为left <= right，并且查找的元素不在有序数组中，则while语句的出界条件是left > right，也就是left == right + 1，写成区间形式就是[right+1,right][right+1,right]，此时待查找区间为空，待查找区间中没有元素存在，此时终止循环时，可以直接返回−1。
    • 比如说区间[3,2]， 此时左边界大于右边界，直接终止循环，返回 −1即可。
  2. 如果判断语句为left < right，并且查找的元素不在有序数组中，则while语句出界条件是left == right，写成区间形式就是[right,right][right,right]。此时区间不为空，待查找区间还有一个元素存在，我们并不能确定查找的元素不在这个区间中，此时终止循环时，如果直接返回−1就是错误的。
    • 比如说区间 [2,2][2,2]，如果元素 nums[2] 刚好就是目标元素 target，此时终止循环，返回 −1 就漏掉了。

但是如果我们还是想要使用 left < right 的话，怎么办？

可以在出界之后增加一层判断，判断 left所指向位置是否等于目标元素，如果是的话就返回 leftlef**t，如果不是的话返回 −1−1。即：

while left < right:
    # ...
return left if nums[left] == target else -1

3.4 搜索区间范围的选择

在进行区间范围选择的时候，通常有三种写法：

  1. left = mid + 1，right = mid - 1。
  2. left = mid + 1 ，right = mid。
  3. left = mid，right = mid - 1。

这是二分查找的一个难点，写错了很容易造成死循环，或者得不到正确结果。

这其实跟二分查找算法的两种不同思路和三种写法有关。

  • 思路 1：「直接法」—— 在循环体中找到元素后直接返回结果。
  • 思路 2：「排除法」—— 在循环体中排除目标元素一定不存在区间。

三、经典例题

34. 在排序数组中查找元素的第一个和最后一个位置open in new window

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：

输入：nums = [], target = 0
输出：[-1,-1]

提示：

  • 0 <= nums.length <= 105
  • -109 <= nums[i] <= 109
  • nums 是一个非递减数组
  • -109 <= target <= 109

这道题就把以上的注意点很好的概括出来的，中间有涉及到mid的取值问题，left，right的取值范围，while的判断条件。

首先这道题是求得是等于target元素的第一的位置和等于target元素的最后一个元素

举例说明

[1, 2, 2, 3, 4, 5, 5]
 0, 1, 2, 3, 4, 5, 6

假如target为5求得也就是[5, 6]

第一次middle = (left + right) // 2为3，区间范围为[middle+1, right]值的范围，我们要时刻保证我们要取的值在[left,right]区间中

  • 目标是找到target在数组中的起始位置。
  • 使用二分查找法，通过调整搜索范围来逼近目标值的开始位置。
  • 当nums[middle] < target时，说明目标值至少在middle + 1及之后，因此将left更新为middle + 1。
  • 否则，当nums[middle] >= target时，缩小右边界至middle，因为目标值可能在middle或其左边。
  • 最终检查left是否指向了目标值，如果是，则返回其索引；否则返回-1表示未找到。
def find_start():
    left, right = 0, len(nums) - 1
    while left < right:
        middle = (left + right) // 2
        
        if nums[middle] < target:
            left = middle + 1
        else:
            right = middle
    return left if nums[left] == target else -1
  • 目标是找到target在数组中的结束位置。
  • 同样使用二分查找法，但为了正确地定位到目标值的最后出现位置，计算中间点middle的方式略有不同：(left + right + 1) // 2。这确保了当left和right相邻时，优先选择右边的元素作为middle，从而避免陷入无限循环。
  • 如果nums[middle] > target，说明目标值最多只到middle - 1，因此将right更新为middle - 1。
  • 否则，当nums[middle] <= target时，移动左边界至middle，以继续向可能的目标值结束位置搜索。
  • 最后检查left是否指向了目标值，如果是，则返回其索引；否则返回-1。
def find_end():
    left, right = 0, len(nums) - 1
    while left < right:
        middle = (left + right + 1) // 2
        if nums[middle] > target:
            right = middle - 1
        else:
            left = middle

    return left if nums[left] == target else -1

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:

        def find_start():
            left, right = 0, len(nums) - 1
            while left < right:
                middle = (left + right) // 2
                if nums[middle] < target:
                    left = middle + 1
                else:
                    right = middle
            return left if nums[left] == target else -1

        def find_end():
            left, right = 0, len(nums) - 1
            while left < right:
                middle = (left + right + 1) // 2
                if nums[middle] > target:
                    right = middle - 1
                else:
                    left = middle

            return left if nums[left] == target else -1

        if not nums:
            return [-1, -1]
        return [find_start(), find_end()]

这种在有序数组中寻找第一个和最后一个位置，也是在很多算法中出现的，可能记起来会比较复杂当然也可以记住一个口诀就是左加右减，右加一

左加：left = middle + 1

右减：right = middle - 1

右加一：middle = (left + right + 1) // 2

0  Words
Comments
  • Latest
  • Oldest
  • Hottest
Powered by Waline v2.15.8
orderlines-blog
Copyright © 2026 Y-aong