从猜数字游戏到LeetCode刷题：用Python二分法解决实际问题的完整思路拆解

从猜数字游戏到LeetCode刷题：用Python二分法解决实际问题的完整思路拆解

想象一下和朋友玩猜数字游戏：对方心里想着1到100之间的一个数字，你每次猜测后，他会告诉你"大了"或"小了"。最笨的方法是挨个猜1,2,3...但聪明人会用二分法——先猜50，排除一半可能性；再根据提示猜25或75，每次都将可能性减半。这种"排除法"思维正是算法中二分查找的核心思想。本文将带你从生活场景出发，逐步掌握用Python实现二分法解决LeetCode经典问题的完整方法论。

1. 二分法基础：从游戏到算法

1.1 生活中的二分法思维

猜数字游戏展示了二分法的三个关键要素：

1. 有序范围：数字在1-100之间有序排列
2. 中间点判断：每次选择当前范围的中间值作为猜测
3. 范围收缩：根据反馈调整搜索范围

这种思维可以迁移到编程中。比如在电话簿找名字，你不会从头翻到尾，而是根据字母顺序快速定位到大概位置，这正是二分查找的现实应用。

# 猜数字游戏的二分法模拟 def guess_number(max_num=100): low, high = 1, max_num while low <= high: mid = (low + high) // 2 feedback = input(f"是{mid}吗？(输入=,>,<): ") if feedback == "=": return mid elif feedback == ">": low = mid + 1 else: high = mid - 1 return -1

1.2 算法中的标准二分查找

LeetCode 704题是标准的二分查找实现。与猜数字游戏相比，算法实现需要注意：

def binary_search(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 -1

关键点：循环条件left <= right确保搜索区间有效，mid计算方式避免整数溢出

2. 问题变形：平方根计算

2.1 从查找问题到近似求解

LeetCode 69题要求计算非负整数的平方根（取整）。这与标准二分查找的区别在于：

1. 搜索空间变化：从数组索引变为连续数值范围
2. 终止条件：不是精确匹配而是满足mid² ≤ x < (mid+1)²

def mySqrt(x): left, right = 0, x res = 0 while left <= right: mid = (left + right) // 2 if mid * mid <= x: res = mid left = mid + 1 else: right = mid - 1 return res

2.2 边界情况处理

实际编码时需要特别注意边界条件：

• x=0或1时的直接返回
• 大数计算时的整数溢出（可用mid <= x // mid代替乘法比较）
• 搜索范围的初始设置（可优化为right=x//2+1）

# 优化后的平方根计算 def mySqrt_optimized(x): if x < 2: return x left, right = 2, x // 2 while left <= right: mid = left + (right - left) // 2 if mid == x // mid: return mid elif mid < x // mid: left = mid + 1 else: right = mid - 1 return right

3. 进阶应用：搜索插入位置

3.1 查找与插入的结合

LeetCode 35题要求在有序数组中查找目标值或确定插入位置。这需要理解二分查找的微妙变化：

• 标准二分查找返回-1表示未找到
• 本题需要返回插入位置，即第一个≥target的索引

def searchInsert(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

3.2 不同实现方式的对比

实践中二分查找有多种写法，主要区别在于区间定义：

选择建议：初学者建议掌握闭区间写法，更符合直觉；熟练后可尝试其他写法理解本质

4. 复杂变形：查找元素边界

4.1 问题分析与转化

LeetCode 34题要求在排序数组中查找元素的起始和结束位置。这需要两次二分查找：

1. 第一次找第一个≥target的位置（左边界）
2. 第二次找第一个>target的位置减1（右边界）

def searchRange(nums, target): def find_left(): left, right = 0, len(nums) - 1 while left <= right: mid = left + (right - left) // 2 if nums[mid] >= target: right = mid - 1 else: left = mid + 1 return left def find_right(): left, right = 0, len(nums) - 1 while left <= right: mid = left + (right - left) // 2 if nums[mid] <= target: left = mid + 1 else: right = mid - 1 return right left_pos = find_left() right_pos = find_right() return [left_pos, right_pos] if left_pos <= right_pos else [-1, -1]

4.2 调试技巧与常见错误

解决边界类问题时容易遇到的陷阱：

1. 空数组处理
2. 目标值不存在的情况
3. 重复元素的处理
4. 指针更新条件错误导致的死循环

调试时可以：

• 打印每次循环的left, right, mid值
• 使用小测试案例手动模拟
• 检查循环终止条件是否完备

# 测试案例设计建议 test_cases = [ ([5,7,7,8,8,10], 8, [3,4]), # 正常情况 ([5,7,7,8,8,10], 6, [-1,-1]), # 不存在 ([], 0, [-1,-1]), # 空数组 ([1], 1, [0,0]), # 单元素 ([2,2], 2, [0,1]) # 全匹配 ]

二分法的威力在于其O(log n)的高效性，但真正掌握需要理解其思想而不仅是记忆模板。从猜数字到解决LeetCode问题，核心都是通过不断排除不可能的区域来缩小搜索范围。建议从简单题目开始实践，逐步培养将实际问题转化为二分查找问题的能力。