binary search

Jessica Gracewell2023-09-282023-09-28

二分查找

第一部分：介绍

什么是二分搜索？
二分搜索（Binary Search）是一种在有序序列中查找特定元素的搜索算法。这种算法每一步都将序列分成两个等份，并判断所查找的元素可能存在的那一半，直至找到目标元素或范围缩小至零。
基本原理
1. **初始化：**设定两个指针，一个表示搜索范围的开始（start），另一个表示搜索范围的结束（end）。
2. **中点计算：**在每一步中，计算范围的中点（mid）并比较中点的值与目标值。
3. 范围缩小：
  - 如果中点的值等于目标值，搜索成功；
  - 如果中点的值小于目标值，说明目标值在中点的右侧，更新开始指针为中点+1；
  - 如果中点的值大于目标值，说明目标值在中点的左侧，更新结束指针为中点-1。
4. **循环或递归：**重复上述步骤，直到找到目标值或搜索范围缩小至零。
时间复杂度
二分搜索的时间复杂度为
O(logn)，其中n是序列的长度。这比线性搜索的时间复杂度 O(n) 要好得多。
使用场景
二分搜索主要应用于有序序列的查找场景，例如在排序数组中查找元素，查找插入位置等。在数据量大而且数据有序的情况下，二分搜索比线性搜索更加高效。
注意事项
二分搜索要求数据必须是有序的，所以在使用前要确保数据已排序。
在实际应用中，二分搜索可能会有多种变体，例如查找左边界、右边界等，需要根据具体需求进行适当的修改。
接下来的部分，我们将通过代码来展示二分搜索的基础模板。

第二部分：基础模板

二分搜索模板
下面是一个基础的二分搜索模板，展示了如何在有序数组中实现二分搜索。

def binary_search(nums, target):
    """
    二分搜索模板
    :param nums: 一个有序的整数列表
    :param target: 需要搜索的目标值
    :return: 如果目标值存在，返回其索引；如果不存在，返回-1。
    """
    # 初始化开始和结束指针
    start, end = 0, len(nums) - 1  # 列表的第一个和最后一个元素的索引
    
    # 当开始指针小于或等于结束指针时，执行循环体内的代码
    while start <= end:
        # 计算中点的索引。使用start + (end - start) // 2 防止整数溢出
        mid = start + (end - start) // 2  # // 表示整数除法
        
        # 比较中点元素与目标值
        if nums[mid] == target:  # 如果中点元素等于目标值，返回中点的索引
            return mid
        elif nums[mid] < target:  # 如果中点元素小于目标值，更新开始指针为中点索引+1
            start = mid + 1
        else:  # 如果中点元素大于目标值，更新结束指针为中点索引-1
            end = mid - 1
    
    # 如果循环结束还没找到目标值，返回-1表示目标值不存在于列表中
    return -1

代码解释
1. 初始化指针：start 和 end 指针分别初始化为列表的开始和结束位置。
2. **计算中点：**在每次循环中，计算 start 和 end 的中点，mid = start + (end - start) // 2 防止整数溢出。
3. **比较中点和目标值：**根据 nums[mid] 与 target 的大小关系，更新 start 或 end 指针，缩小搜索范围。
4. **循环直至找到或范围缩小至0：**如果 start 指针大于 end 指针，表示搜索范围已无元素，结束搜索。
示例
下面我们用一个简单的例子来测试上面的代码。

nums = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
target = 15

# 调用二分搜索函数
index = binary_search(nums, target)

# 输出结果
if index != -1:
    print(f"目标值 {target} 在列表中的索引为 {index}。")
else:
    print(f"目标值 {target} 不在列表中。")

这个例子将输出 “目标值 15 在列表中的索引为 7。”，因为 15 是列表中的第7个元素（索引从0开始）。

第三部分：查找边界

查找左边界
查找左边界指的是在有序数组中找到目标值的第一次出现的位置。下面是实现查找左边界的Python代码。

python

def binary_search_left(nums, target):
    """
    在有序数组中二分查找目标值的最左侧位置
    :param nums: 一个有序的整数列表
    :param target: 需要搜索的目标值
    :return: 目标值最左侧的索引，如果目标值不存在，返回-1。
    """
    start, end = 0, len(nums) - 1  # 初始化开始和结束指针
    
    while start <= end:  # 当开始指针小于或等于结束指针时，执行循环体内的代码
        mid = start + (end - start) // 2  # 计算中点的索引
        
        if nums[mid] < target:  # 如果中点元素小于目标值，更新开始指针为中点索引+1
            start = mid + 1
        else:  # 如果中点元素大于等于目标值，更新结束指针为中点索引-1
            end = mid - 1
    
    # 检查开始指针是否越界，并且是否指向目标值
    if start < len(nums) and nums[start] == target:
        return start  # 返回目标值最左侧的索引
    else:
        return -1  # 如果目标值不存在，返回-1

查找右边界
查找右边界指的是在有序数组中找到目标值的最后一次出现的位置。下面是实现查找右边界的Python代码。

def binary_search_right(nums, target):
    """
    在有序数组中二分查找目标值的最右侧位置
    :param nums: 一个有序的整数列表
    :param target: 需要搜索的目标值
    :return: 目标值最右侧的索引，如果目标值不存在，返回-1。
    """
    start, end = 0, len(nums) - 1  # 初始化开始和结束指针
    
    while start <= end:  # 当开始指针小于或等于结束指针时，执行循环体内的代码
        mid = start + (end - start) // 2  # 计算中点的索引
        
        if nums[mid] <= target:  # 如果中点元素小于等于目标值，更新开始指针为中点索引+1
            start = mid + 1
        else:  # 如果中点元素大于目标值，更新结束指针为中点索引-1
            end = mid - 1
    
    # 检查结束指针是否越界，并且是否指向目标值
    if end >= 0 and nums[end] == target:
        return end  # 返回目标值最右侧的索引
    else:
        return -1  # 如果目标值不存在，返回-1

示例
下面我们用一个简单的例子来测试查找左边界和右边界的代码。

nums = [2, 4, 4, 4, 6, 7, 8]
target = 4

# 调用二分搜索函数
left_index = binary_search_left(nums, target)
right_index = binary_search_right(nums, target)

# 输出结果
if left_index != -1 and right_index != -1:
    print(f"目标值 {target} 在列表中的最左侧索引为 {left_index}，最右侧索引为 {right_index}。")
else:
    print(f"目标值 {target} 不在列表中。")

这个例子将输出 “目标值 4 在列表中的最左侧索引为 1，最右侧索引为 3。”，因为 4 在列表中从索引 1 到索引 3 连续出现了三次。

第四部分：扩展：非常规二分搜索

在浮点数上使用二分搜索
二分搜索不仅可以应用于整数数组，还可以应用于浮点数，用于求解精度问题。以下是一个简单的例子，通过二分搜索算法求解平方根。

def binary_search_sqrt(x, precision=1e-6):
    """
    使用二分搜索求解平方根
    :param x: 输入值
    :param precision: 精度，默认为1e-6
    :return: x的平方根，精确到precision
    """
    if x < 0:  # 负数没有实数平方根
        return None
    
    start, end = 0, x  # 对于x>=1，其平方根位于[1,x]之间；对于0<x<1，其平方根位于[x,1]之间
    if x < 1:
        end = 1
    
    while end - start > precision:  # 当结束指针和开始指针之间的差值大于precision时，继续执行循环体内的代码
        mid = start + (end - start) / 2  # 计算中点的值
        if mid * mid > x:  # 如果中点的平方大于x，更新结束指针为中点
            end = mid
        else:  # 如果中点的平方小于等于x，更新开始指针为中点
            start = mid
    
    return start  # 返回计算得到的平方根值

旋转数组的二分搜索
对于一个旋转的有序数组，也可以利用二分搜索来找到一个元素。旋转的有序数组是指一个原本有序的数组在某个点进行了旋转。

例如4,5,6,7,0,1,2 是数组 0,1,2,4,5,6,7 在索引 3 处进行旋转得到的。

下面是在旋转数组中进行二分搜索的代码：

def search_rotated_array(nums, target):
    """
    在旋转的有序数组中二分查找目标值
    :param nums: 一个经过旋转的有序整数列表
    :param target: 需要搜索的目标值
    :return: 如果目标值存在，返回其索引；如果不存在，返回-1。
    """
    start, end = 0, len(nums) - 1  # 初始化开始和结束指针
    
    while start <= end:  # 当开始指针小于或等于结束指针时，执行循环体内的代码
        mid = start + (end - start) // 2  # 计算中点的索引
        
        if nums[mid] == target:  # 如果中点元素等于目标值，返回中点的索引
            return mid
        
        if nums[start] <= nums[mid]:  # 如果开始元素小于等于中点元素，说明左侧是有序的
            if nums[start] <= target < nums[mid]:  # 如果目标值在有序的范围内，更新结束指针为中点索引-1
                end = mid - 1
            else:  # 如果目标值不在有序的范围内，更新开始指针为中点索引+1
                start = mid + 1
        else:  # 如果开始元素大于中点元素，说明右侧是有序的
            if nums[mid] < target <= nums[end]:  # 如果目标值在有序的范围内，更新开始指针为中点索引+1
                start = mid + 1
            else:  # 如果目标值不在有序的范围内，更新结束指针为中点索引-1
                end = mid - 1
    
    return -1  # 如果目标值不存在，返回-1

第五部分：优化和变体

三分搜索
三分搜索是二分搜索的一种变体，它每次将数组分成三个部分，而不是两个。三分搜索通常用于查找未知函数的局部最大值或最小值。

下面是一个简单的三分搜索算法的Python实现，用于查找一元函数的局部最小值。

def ternary_search(func, left, right, precision=1e-6):
    """
    使用三分搜索寻找一元函数的局部最小值
    :param func: 目标函数
    :param left: 搜索区间左侧界限
    :param right: 搜索区间右侧界限
    :param precision: 搜索精度，默认为1e-6
    :return: 函数的局部最小值点
    """
    while right - left > precision:
        m1 = left + (right - left) / 3
        m2 = right - (right - left) / 3
        
        f1, f2 = func(m1), func(m2)
        if f1 < f2:
            right = m2
        else:
            left = m1
    return (left + right) / 2

二分搜索的优化
在某些场景下，我们可以对二分搜索进行优化，以减少比较次数或解决更复杂的问题。例如，我们可以通过比较中点和两端点的大小关系，快速判断目标值可能位于的区间，从而减少不必要的比较。
复杂数据结构中的二分搜索
二分搜索不仅可以应用于一维数组，还可以扩展到更复杂的数据结构中，例如，用于查找二维矩阵中的元素，或者在图和树结构中查找路径等。

下面是一个在有序二维矩阵中进行二分搜索的Python代码示例：

def search_matrix(matrix, target):
    """
    在有序二维矩阵中二分查找目标值
    :param matrix: 一个每行和每列都有序的二维矩阵
    :param target: 需要搜索的目标值
    :return: 如果目标值存在，返回True；如果不存在，返回False。
    """
    if not matrix or not matrix[0]:
        return False
    
    rows, cols = len(matrix), len(matrix[0])
    row, col = 0, cols - 1  # 从右上角开始搜索
    
    while row < rows and col >= 0:
        if matrix[row][col] == target:
            return True
        elif matrix[row][col] < target:
            row += 1  # 下移
        else:
            col -= 1  # 左移
    return False

第六部分：实例和应用

查找插入位置
二分搜索可以用来找到一个数值应该被插入到有序数组的哪个位置，以维持数组的有序性。以下是Python代码：

def search_insert_position(nums, target):
    """
    在有序数组中查找目标值的插入位置
    :param nums: 一个有序的整数列表
    :param target: 需要搜索的目标值
    :return: 目标值应该被插入的位置
    """
    start, end = 0, len(nums) - 1  # 初始化开始和结束指针
    
    while start <= end:  # 当开始指针小于或等于结束指针时，执行循环体内的代码
        mid = start + (end - start) // 2  # 计算中点的索引
        
        if nums[mid] == target:  # 如果中点元素等于目标值，返回中点的索引
            return mid
        elif nums[mid] < target:  # 如果中点元素小于目标值，更新开始指针为中点索引+1
            start = mid + 1
        else:  # 如果中点元素大于目标值，更新结束指针为中点索引-1
            end = mid - 1
    
    return start  # 返回开始指针，表示目标值应该被插入的位置

寻找旋转数组的最小值
对于一个旋转过的有序数组，我们可以使用二分搜索来找到数组中的最小值。以下是Python代码：

def find_min_in_rotated_array(nums):
    """
    在旋转的有序数组中查找最小值
    :param nums: 一个经过旋转的有序整数列表
    :return: 数组中的最小值
    """
    start, end = 0, len(nums) - 1  # 初始化开始和结束指针
    
    while start < end:  # 当开始指针小于结束指针时，执行循环体内的代码
        mid = start + (end - start) // 2  # 计算中点的索引
        
        if nums[mid] > nums[end]:  # 如果中点元素大于结束元素，最小值在右侧，更新开始指针为中点索引+1
            start = mid + 1
        else:  # 如果中点元素小于等于结束元素，最小值在左侧，更新结束指针为中点索引
            end = mid
    
    return nums[start]  # 返回最小值

示例
我们可以通过以下例子来测试上述函数：

nums1 = [1, 3, 5, 7]
target1 = 2
print(search_insert_position(nums1, target1))  # 输出：1，因为2应该被插入到索引1的位置

nums2 = [4, 5, 6, 0, 1, 2]
print(find_min_in_rotated_array(nums2))  # 输出：0，因为0是数组中的最小值

通过这些实际的例子，我们可以看到二分搜索算法在各种场景下的应用，以及如何通过对基础模板的修改和优化来解决更复杂的问题。

第七部分：更多典型案例

寻找峰值
峰值元素是指其值大于或等于相邻值的元素。给定一个输入数组 nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。

以下是Python代码：

def find_peak_element(nums):
    """
    在数组中查找峰值元素的索引
    :param nums: 输入的整数列表，nums[i] ≠ nums[i+1]
    :return: 峰值元素的索引
    """
    # 初始化开始和结束指针
    start, end = 0, len(nums) - 1
    
    # 当开始指针小于结束指针时，执行循环体内的代码
    while start < end:
        # 计算中点的索引
        mid = start + (end - start) // 2
        
        # 比较中点元素和它右侧的元素
        if nums[mid] < nums[mid + 1]:  # 如果中点元素小于它右侧的元素，峰值在右侧，更新开始指针为中点索引+1
            start = mid + 1
        else:  # 如果中点元素大于等于它右侧的元素，峰值在左侧，更新结束指针为中点索引
            end = mid
    
    # 返回峰值元素的索引
    return start

第一个错误的版本
假设你有一个版本号从 1 到 n 的产品，其中存在一个错误的版本，导致所有大于该版本号的版本都是错误的。给定一个 isBadVersion(version) 的API，它会返回版本号 version 是否错误。实现一个函数来查找第一个错误的版本。

以下是Python代码：

def first_bad_version(n, isBadVersion):
    """
    使用二分搜索查找第一个错误的版本
    :param n: 版本的总数
    :param isBadVersion: 一个函数，输入版本号，返回该版本是否错误
    :return: 第一个错误的版本号
    """
    # 初始化开始和结束指针
    start, end = 1, n
    
    # 当开始指针小于结束指针时，执行循环体内的代码
    while start < end:
        # 计算中点的索引
        mid = start + (end - start) // 2
        
        # 调用API检查中点版本是否错误
        if isBadVersion(mid):  # 如果中点版本错误，更新结束指针为中点索引
            end = mid
        else:  # 如果中点版本正确，更新开始指针为中点索引+1
            start = mid + 1
    
    # 返回第一个错误的版本号
    return start

示例

# 示例1：寻找峰值
nums = [1, 2, 3, 1]
print(find_peak_element(nums))  # 输出：2，因为nums[2]是峰值元素

# 示例2：第一个错误的版本
def isBadVersion(version):
    return version >= 4  # 假设第4个版本开始是错误的

print(first_bad_version(5, isBadVersion))  # 输出：4，因为第4个版本是第一个错误的版本