二分法（总体概述）

基础概念

二分法是一种在有序数组（或列表）中查找目标值的算法。它的基本思想是通过逐步缩小查找范围，快速定位目标值。

二分法的步骤

1. 初始化查找范围：设定左边界left和右边界right。
2. 计算中间位置：找到中间位置mid，通常是mid = left + (right - left) // 2。
3. 比较中间值：将中间位置的值与目标值进行比较：
   • 如果中间值等于目标值，返回其位置。
   • 如果中间值小于目标值，调整左边界到mid + 1。
   • 如果中间值大于目标值，调整右边界到mid - 1。
4. 重复步骤2和3，直到找到目标值或查找范围为空（即left > right）。

基本实现

以下是一个基本的二分查找实现：

def binary_search(arr, target):
    """ 二分查找算法
    :param arr: 已排序的数组
    :param target: 要查找的目标值
    :return: 目标值的索引，如果未找到则返回-1
    """
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = left + (right - left) // 2  # 优化后的中间值计算方式
        if arr[mid] == target:
            return mid  # 找到目标值，返回其索引
        elif arr[mid] < target:
            left = mid + 1  # 目标值在右侧，调整左边界
        else:
            right = mid - 1  # 目标值在左侧，调整右边界
    
    return -1  # 未找到目标值

# 测试二分查找算法
arr = [1, 3, 5, 7, 9, 11, 13, 15]
target = 7
result = binary_search(arr, target)
print(f"目标值 {target} 的索引位置为: {result}")

高级例题

1. 求解平方根：使用二分法求一个非负整数的平方根，允许一定的误差范围。

   def sqrt(x):
       """ 使用二分法求平方根
       :param x: 非负整数
       :return: 平方根值
       """
       if x < 0:
           return -1  # 对于负数，返回-1表示错误
       left, right = 0, x
       precision = 1e-7  # 精度
       while right - left > precision:
           mid = left + (right - left) / 2
           if mid * mid > x:
               right = mid
           else:
               left = mid
       return left
   
   # 测试
   print(sqrt(9))  # 输出接近于3
   

2. 找出旋转排序数组中的最小值：在一个旋转排序数组中找到最小值。

   def find_min(nums):
       """ 找出旋转排序数组中的最小值
       :param nums: 旋转排序数组
       :return: 最小值
       """
       left, right = 0, len(nums) - 1
       while left < right:
           mid = left + (right - left) // 2
           if nums[mid] > nums[right]:
               left = mid + 1
           else:
               right = mid
       return nums[left]
   
   # 测试
   nums = [4, 5, 6, 7, 0, 1, 2]
   print(find_min(nums))  # 输出0
   

3. 在排序数组中查找元素的第一个和最后一个位置：

   def find_first_last(nums, target):
       """ 查找元素的第一个和最后一个位置
       :param nums: 排序数组
       :param target: 目标值
       :return: 元素的第一个和最后一个位置的索引元组
       """
       def find_position(is_first):
           left, right = 0, len(nums) - 1
           result = -1
           while left <= right:
               mid = left + (right - left) // 2
               if nums[mid] == target:
                   result = mid
                   if is_first:
                       right = mid - 1  # 查找第一个位置
                   else:
                       left = mid + 1  # 查找最后一个位置
               elif nums[mid] < target:
                   left = mid + 1
               else:
                   right = mid - 1
           return result
   
       first = find_position(True)
       last = find_position(False)
       return (first, last)
   
   # 测试
   nums = [5, 7, 7, 8, 8, 10]
   target = 8
   print(find_first_last(nums, target))  # 输出(3, 4)