查找算法/搜索 | 二分法（python）

Hi，大家好，我是半亩花海。近期在学习算法与数据结构相关知识，纯纯小白，欢迎一起交流呀。打算从算法学起，首先学习查找算法（搜索）中的二分法，我使用的是 python 语言进行学习。本算法学习参考了很多博主的文章，比如：算法第三期——二分法（Python）_python二分法-CSDN博客、玩转二分法（python版）——leetcode二分法题总结【简单易懂】_len(nums) - 1-CSDN博客、Python实现二分法搜索_二分法python-CSDN博客以及 LeetCode 等等。

一、二分法概述

1.1 理论背景：非线性方程的求根问题

1.2 使用条件

1.3 复杂度分析

二、二分法求解方法

2.1 基本思想

2.2 代码模板

2.2.1 闭区间：[left, right]

2.2.2 左闭右开区间：[left, right)

2.2.3 开区间：(left, right)

三、二分法例题

1. LeetCode[704.二分查找]【简单】

方法一：暴力法

方法二：二分查找法

2. LeetCode[69.x的平方根]【简单】

方法：二分查找法

3. LeetCode[35.搜索插入位置]【简单】

方法：二分查找法

4. LeetCode[34.在排序数组中查找元素的第一个和最后一个位置]【中等】

方法一：暴力法

方法二：二分查找法

一、二分法概述

在一个有序序列中查找某个元素，在之前我们可以使用暴力法来遍历序列，直至找到该元素，复杂度是 $O(n)$ ，但其实可以利用序列有序的特征进行折半查找。

二分法定义：把一个长度为 $n$ 的有序序列上 $O(n)$ 的查找时间，优化到了 $O(logn)$ 。
二分法本质：折半搜索。
二分法效率：很高，时间复杂度为 $O(logn)$ （其实不太严谨，因为需要考虑底数，那就要看分治的复杂度：二分法底数为 2，则为复杂度为 $O(log_{2}n)$ ；三分法底数为 3，则为 $O(log_{3}n)$ ... 以此类推。当然不写底数也行，但是得知道它有底数）。
二分法实例——猜数游戏：若 $n=1000$ 万，只需要猜 $\log_{2}10^{7}\approx 24$ 次。

1.1 理论背景：非线性方程的求根问题

满足方程： $f(x)=0$ 的数 $x$ 称为方程的根。
非线性方程：指 $f(x)$ 中含有三角函数、指数函数或其他超越函数。很难或者无法求得精确解。二分法是一种求解的方法。

1.2 使用条件

上下界 [a, b] 确定
函数在 [a, b] 内单调

1.3 复杂度分析

$n$ 次二分后，区间缩小到 $\frac{b-a}{2^{n}}$
给定 $a, b$ 和精度要求 $\xi$ ，可以算出二分次数 $n$ ，即满足： $\frac{b-a}{2^{n}}< \xi$
二分法的复杂度：
- 时间复杂度： $O(logn)$ ，其中 $n$ 是数组的长度。
- 空间复杂度： $O(1)$
示例：如果函数在区间 $[0,10^{5}]$ 内单调变化，要求根的精度是 $10^{-8}$ ，那么二分次数是 44 次。因为： $\frac{10^{5}-0}{2^{n}}< 10^{-8} = > 2^{n}> 10^{13} = > n> log_{2}10^{13} = > n\approx 44$

二、二分法求解方法

2.1 基本思想

首先把循环可以进行的条件写成 while left <= right，在退出循环的时候，一定有 left == right 成立，此时返回 nums[mid] 中对应的 mid 即可。

深层次的思想是“夹逼法”或者称为“排除法”——二分查找算法的基本思想。
“排除法”：在每一轮循环中排除一半以上的元素，于是在对数级别的时间复杂度内，就可以把区间“夹逼”只剩下 1 个数，而这个数是不是我们要找的数，单独做一次判断就可以了。

2.2 代码模板

下面的代码包含闭区间、左闭右开区间和开区间三种写法。选择自己喜欢的一种写法即可。

binary_search 返回最小的满足 nums[i] >= target 的 i
如果数组为空，或者所有数都小于 target，则返回 len(nums)
要求 nums 是非递减的，即 nums[i] <= nums[i + 1]

2.2.1 闭区间：[left, right]

# 闭区间写法
def binary_search1(nums, target):
    left, right = 0, len(nums) - 1  # 闭区间 [left, right]
    while left <= right:  # 区间不为空
        # 循环不变量：
        # nums[left-1] < target
        # nums[right+1] >= target
        mid = (left + right) // 2
        if nums[mid] < target:
            left = mid + 1  # 范围缩小到 [mid+1, right]
        else:
            right = mid - 1  # 范围缩小到 [left, mid-1]
    return left

2.2.2 左闭右开区间：[left, right)

# 左闭右开区间写法
def binary_search2(nums, target):
    left = 0
    right = len(nums)  # 左闭右开区间 [left, right)
    while left < right:  # 区间不为空
        # 循环不变量：
        # nums[left-1] < target
        # nums[right] >= target
        mid = (left + right) // 2
        if nums[mid] < target:
            left = mid + 1  # 范围缩小到 [mid+1, right)
        else:
            right = mid  # 范围缩小到 [left, mid)
    return left  # 返回 left 还是 right 都行，因为循环结束后 left == right

2.2.3 开区间：(left, right)

# 开区间写法
def binary_search3(nums: List[int], target: int) -> int:
    left, right = -1, len(nums)  # 开区间 (left, right)
    while left + 1 < right:  # 区间不为空
        mid = (left + right) // 2
        # 循环不变量：
        # nums[left] < target
        # nums[right] >= target
        if nums[mid] < target:
            left = mid  # 范围缩小到 (mid, right)
        else:
            right = mid  # 范围缩小到 (left, mid)
    return right

三、二分法例题

基本模板就是这样，接下来就是实践，积累经验。目前做过的 LeetCode 题有：704、69、35、34（后面会继续写153、33、81、154、4）。推荐按照这个顺序做题（难度从易到难）。

1. LeetCode[704.二分查找]【简单】

题目：

给定一个 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

思路及题解：

方法一：暴力法

def binary_search(nums, target):
    for i in range(len(nums)):
        if nums[i] == target:
            return i
    return -1

# nums = [-1, 0, 3, 5, 9, 12]
# target1 = 9
# target2 = 2
'''使用input()函数输入：
nums = eval(input("nums = "))
target1 = int(input("target1 = "))
target2 = int(input("target2 = "))
'''
# print(binary_search(nums, target1))  # 输出：4
# print(binary_search(nums, target2))  # 输出：-1

方法二：二分查找法

（1）思路

在升序数组 $nums$ 中寻找目标值 $target$ ，对于特定下标 $i$ ，比较 $nums[i]$ 和 $target$ 的大小：

如果 $nums[i]=target$ ，则下标 $i$ 即为要寻找的下标；
如果 $nums[i]>target$ ，则 $target$ 只可能在下标 $i$ 的左侧；
如果 $nums[i]<target$ ，则 $target$ 只可能在下标 $i$ 的右侧。

基于上述事实，可以在有序数组中使用二分查找寻找目标值，分为以下三步：

① 定义查找的范围 $[left,right]$ （这里的 left 和 right 是索引），初始查找范围是整个数组。

二分查找的条件是查找范围不为空，即 $left\leq right$ 。如果 $target$ 在数组中，二分查找可以保证找到 $target$ ，返回 $target$ 在数组中的下标。如果 $target$ 不在数组中，则当 $left>right$ 时结束查找，返回 $-1$ 。由于每次查找都会将查找范围缩小一半，因此二分查找的时间复杂度是 $O(logn)$ ，其中 $n$ 是数组的长度。

② 每次取查找范围的中点 $mid$ ，比较 $nums[mid]$ 和 $target$ 的大小。

中间索引 $mid$ 有两种写法：

$mid = (left+right)//2$
$mid = left+(right-left)//2$

由于整数运算没有溢出问题，因此通常两种写法都可以使用。第二种写法更为安全，以确保在边界条件下也能正常工作，特别是当 $left$ 和 $right$ 都很大的时候。

③ 如果 $nums[mid]$ 和 $target$ 的大小相等，则 $mid$ 即为要寻找的下标；如果两者不相等，则根据 $nums[mid]$ 和 $target$ 的大小关系将查找范围缩小一半：

$nums[mid]\geq target$ 时： $target$ 在 $mid$ 的左边，新的搜索区间是左半部分， $left$ 不变，更新 $right = mid$ 。
$nums[mid]< target$ 时： $target$ 在 $mid$ 的右边，新的搜索区间是右半部分， $right$ 不变，更新 $left = mid +1$ 。

代码执行完毕直至 $left= right$ ，则此时两者相等，即此时为 $target$ 所处的位置。

（2）题解

class BinarySearch(object):
    def binary_search(self, nums, target):
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (right - left) // 2 + left
            # mid = (left + right) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] > target:
                right = mid - 1
            else:
                left = mid + 1
        return -1

# search = BinarySearch()
# nums = [-1, 0, 3, 5, 9, 12]
# target = 9
# print(search.binary_search(nums, target))  # 输出：4

2. LeetCode[69.x的平方根]【简单】

题目：

给你一个非负整数 $x$ ，计算并返回 $x$ 的 算术平方根 。

由于返回类型是整数，结果只保留整数部分，小数部分将被舍去。

注意：不允许使用任何内置指数函数和算符，例如 $pow(x, 0.5)$ 或者 $x ** 0.5$ 。

示例 1：

输入：x = 4
输出：2

示例 2：

输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

思路及题解：

方法：二分查找法

（1）思路

由于 $x$ 平方根的整数部分 $ans$ 是满足 $k^2 \leq x$ 的最大 $k$ 值，因此我们可以对 $k$ 进行二分查找，从而得到答案。

二分查找的下界为 $0$ ，上界可以粗略地设定为 $x$ 。在二分查找的每一步中，我们只需要比较中间元素 $mid$ 的平方与 $x$ 的大小关系，并通过比较的结果调整上下界的范围。由于我们所有的运算都是整数运算，不会存在误差，因此在得到最终的答案 $ans$ 后，也就不需要再去尝试 $ans+1$ 了。

（2）题解

class Solution(object):
    def mySqrt(self, x):
        left, right, ans = 0, x, -1
        while left <= right:
            mid = (left + right) // 2
            if mid * mid <= x:
                ans = mid
                left = mid + 1
            else:
                right = mid - 1
        return ans

# mysqrt = Solution()
# x = 8
# print(mysqrt.mySqrt(x))  # 输出：2

3. LeetCode[35.搜索插入位置]【简单】

题目：

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 $O(logn)$ 的算法。

示例 1：

输入：nums = [1,3,5,6], target = 5
输出：2

示例 2：

输入：nums = [1,3,5,6], target = 2
输出：1

示例 3：

输入：nums = [1,3,5,6], target = 7
输出：4

思路及题解：

方法：二分查找法

（1）思路

考虑这个插入的位置 $pos$ ，它成立的条件为：

$nums[pos-1]< target\leq nums[pos]$

其中 $nums$ 代表排序数组。由于如果存在这个目标值，我们返回的索引也是 $pos$ ，因此我们可以将两个条件合并得出最后的目标：「在一个有序数组中找第一个大于等于 $pos$ 的下标」。

问题转化到这里，直接套用二分法即可，即不断用二分法逼近查找第一个大于等于 $target$ 的下标。下文给出的代码是笔者习惯的二分写法， $ans$ 初值设置为数组长度可以省略边界条件的判断，因为存在一种情况是 $target$ 大于数组中的所有数，此时需要插入到数组长度的位置。

（2）题解

class Solution(object):
    def searchInsert(self, nums, target):
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return left

# solution = Solution()
# nums = [1, 3, 5, 6]
# target = 2
# print(solution.searchInsert(nums, target))  # 输出：1

4. LeetCode[34.在排序数组中查找元素的第一个和最后一个位置]【中等】

题目：

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

如果数组中不存在目标值 $target$ ，返回 $[-1, -1]$ 。你必须设计并实现时间复杂度为 $O(logn)$ 的算法解决此问题。

示例 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]

思路及题解：

方法一：暴力法

（1）思路

① 定义 $left$ 、 $right$ 初始值为 $-1$ ，利用数组有序的特点从头到尾遍历列表，先寻找 $left$ 再寻找 $right$ ，最后 $return [left, right]$ ；

② 在遍历的开始，检查遍历到的元素是否等于 $target$ ，遇到刚好等于 $target$ 的时候，记录当前的位置；

③ 接着遍历，检查遍历到的元素是否不等于 $target$ ，遇到刚好不等于 $target$ 的时候，记录当前位置的前一个位置即可。

（2）复杂度分析

时间复杂度： $O(n)$ ，其中 $n$ 为数组的长度。
空间复杂度： $O(1)$ ，只用到常数个临时变量。

（3）题解

def searchRange(nums, target):
    if not nums:  # 数组为空
        return [-1, -1]
    left, right = -1, -1
    for i in range(len(nums)):
        if nums[i] == target:
            if left == -1:
                left = i
            right = i
    return [left, right]

# nums = [5, 7, 7, 8, 8, 10]
# target = 8
# print(searchRange(nums, target))  # 输出：[3, 4]

方法二：二分查找法

（1）思路

目标元素 $target$ 在有序数组中很可能存在多个；
使用二分查找方法看到的处在中间位置的元素的值 $nums[mid]$ 恰好等于目标元素 $target$ 的时候，还需要继续查找下去；
此时比较容易陷入的误区是线性查找，正确的做法是继续二分查找。

① 初始化 $l, r$ 左右指针，循环条件设为“当 $l < r$ ”。这样设立是因为跳出循环的时候总是有 $l=r$ ，不用思考是 $l$ 还是 $r$ ；

② 取中值。取中左还是中右，这就需要看情况了。如果我们想要找目标值的起始下标，那么当 $nums[mid]$ 大于目标值 $target$ （或者找到这个目标值的时候），右边界都要缩小。即当 $nums[mid] \geq target$ 的时候， $r = mid$ 。

注意：不能以 $mid-1$ 这样的形式缩小，否则当找到起始下标的时候还得再减 1，就会出现问题。因为不可以左右两个都 $=mid$ ，必须有一个 $=mid+1$ ，否则会陷入死循环。所以在其他情况下，左边界 $=mid+1$ 。

③ $mid$ 取左中还是右中，要以你选择哪个是 $mid+1$ 来定。对于第一个循环，这里我们选了 $mid+1$ 的是左边 $l$ ，所以我们要取左中值。否则会陷入死循环。

（2）题解

class Solution(object):
    def searchRange(self, nums, target):
        l, r = 0, len(nums) - 1  # 取起始下标
        while l < r:
            mid = (l + r) // 2
            if nums[mid] >= target:
                r = mid
            else:
                l = mid + 1

        if not nums or nums[l] != target:  # 数组为空或没找到
            return [-1, -1]

        a, b = l, len(nums) - 1  # 取结束下标
        while a < b:
            mid = (a + b + 1) // 2
            if nums[mid] <= target:
                a = mid
            else:
                b = mid - 1

        return [l, a]

# solution = Solution()
# nums = eval(input('nums = '))
# target = int(input('target = '))
# print(solution.search_Range(nums, target))  # 输出：[3, 4]