binary search

二分查找

第一部分：介绍

  1. 什么是二分搜索？
    二分搜索（Binary Search）是一种在有序序列中查找特定元素的搜索算法。这种算法每一步都将序列分成两个等份，并判断所查找的元素可能存在的那一半，直至找到目标元素或范围缩小至零。

  2. 基本原理

    1. 初始化：设定两个指针，一个表示搜索范围的开始（start），另一个表示搜索范围的结束（end）。
    2. 中点计算：在每一步中，计算范围的中点（mid）并比较中点的值与目标值。
    3. 范围缩小：
      • 如果中点的值等于目标值，搜索成功；
      • 如果中点的值小于目标值，说明目标值在中点的右侧，更新开始指针为中点+1；
      • 如果中点的值大于目标值，说明目标值在中点的左侧，更新结束指针为中点-1。
    4. 循环或递归：重复上述步骤，直到找到目标值或搜索范围缩小至零。

  3. 时间复杂度
    二分搜索的时间复杂度为
    O(logn)，其中n是序列的长度。这比线性搜索的时间复杂度 O(n) 要好得多。

  4. 使用场景
    二分搜索主要应用于有序序列的查找场景，例如在排序数组中查找元素，查找插入位置等。在数据量大而且数据有序的情况下，二分搜索比线性搜索更加高效。

  5. 注意事项
    二分搜索要求数据必须是有序的，所以在使用前要确保数据已排序。
    在实际应用中，二分搜索可能会有多种变体，例如查找左边界、右边界等，需要根据具体需求进行适当的修改。
    接下来的部分，我们将通过代码来展示二分搜索的基础模板。

第二部分：基础模板

  1. 二分搜索模板
    下面是一个基础的二分搜索模板，展示了如何在有序数组中实现二分搜索。
    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

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

    第三部分：查找边界

  4. 查找左边界
    查找左边界指的是在有序数组中找到目标值的第一次出现的位置。下面是实现查找左边界的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

  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

  2. 示例
    下面我们用一个简单的例子来测试查找左边界和右边界的代码。
    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 连续出现了三次。

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

  1. 在浮点数上使用二分搜索
    二分搜索不仅可以应用于整数数组，还可以应用于浮点数，用于求解精度问题。以下是一个简单的例子，通过二分搜索算法求解平方根。
    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  # 返回计算得到的平方根值

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

例如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

第五部分：优化和变体

  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

  1. 二分搜索的优化
    在某些场景下，我们可以对二分搜索进行优化，以减少比较次数或解决更复杂的问题。例如，我们可以通过比较中点和两端点的大小关系，快速判断目标值可能位于的区间，从而减少不必要的比较。

  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

第六部分：实例和应用

  1. 查找插入位置
    二分搜索可以用来找到一个数值应该被插入到有序数组的哪个位置，以维持数组的有序性。以下是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  # 返回开始指针，表示目标值应该被插入的位置

  2. 寻找旋转数组的最小值
    对于一个旋转过的有序数组，我们可以使用二分搜索来找到数组中的最小值。以下是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]  # 返回最小值

  3. 示例
    我们可以通过以下例子来测试上述函数：
    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是数组中的最小值

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

    第七部分：更多典型案例

  4. 寻找峰值
    峰值元素是指其值大于或等于相邻值的元素。给定一个输入数组 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. 第一个错误的版本
    假设你有一个版本号从 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个版本是第一个错误的版本


通过这些更多的例子，我们可以进一步理解如何灵活应用二分搜索算法来解决各种实际问题。

第八部分：总结

  1. 知识回顾
    本文详细介绍了二分搜索算法，包括其基本原理、实现模板和多种变体。二分搜索是一种高效的搜索算法，用于在有序序列中查找特定元素，其时间复杂度为 O(logn)。通过二分搜索，我们不仅可以快速定位目标值，还可以解决一系列与查找、定位和优化相关的问题。

  2. 学到的知识

  • 基础模板：我们学习了二分搜索的基础模板，理解了如何通过循环或递归在有序数组中定位目标值。
  • 查找边界：我们探讨了如何修改基础模板来查找目标值的左边界和右边界。
  • 非常规应用：我们学习了如何在浮点数和旋转数组上应用二分搜索。
  • 优化和变体：我们了解了三分搜索和在复杂数据结构中应用二分搜索的方法。
  • 实例和应用：我们通过多个实例学习了二分搜索在实际问题中的应用，如查找插入位置和寻找旋转数组的最小值。
  • 更多典型案例：我们进一步探索了二分搜索在寻找峰值和查找第一个错误版本等问题上的应用。
  1. 总结
    二分搜索是一种极为实用和高效的算法。通过掌握其基础模板和理解其核心原理，我们可以灵活地应用和扩展这一算法，解决各种查找和优化问题。无论是在有序数组、浮点数、旋转数组还是更复杂的数据结构中，二分搜索都能展现出其强大的查找能力。

希望本文的详细解释和丰富实例能帮助读者更好地理解和掌握二分搜索算法，并能灵活运用到实际的编程问题中。在未来的学习和实践中，不妨尝试将二分搜索与其他算法和数据结构结合，探索更多有趣和高效的解决方案。