1. 二分算法核心思想解析二分查找算法是计算机科学中最基础也最高效的搜索算法之一其时间复杂度为O(log n)。这个看似简单的算法背后蕴含着分治思想的精髓——通过每次将问题规模减半来快速缩小搜索范围。在实际编码面试中二分查找类题目出现频率高达27%根据LeetCode题库统计但正确率却不足40%。主要难点在于边界条件的处理、循环终止条件的判断以及特殊情况的处理。我见过太多候选人因为while循环条件写成left right还是left right而功亏一篑。关键理解二分法的本质是逐步缩小搜索空间每次操作后保证目标元素一定存在于剩余的搜索范围内。这个不变量的维护是算法正确性的核心。2. 标准二分查找实现详解2.1 基础模板代码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这个模板有几个关键点需要注意循环条件使用确保能处理单元素情况mid计算采用防溢出写法每次移动left或right时都要跳过mid避免死循环2.2 边界条件分析当处理边界时最容易出现两种错误无限循环通常是因为left和right更新不当遗漏元素循环终止条件设置错误我建议在纸上画出以下测试用例的搜索过程单元素数组双元素数组目标在首位/末位目标不存在3. 二分查找变种题型3.1 寻找左边界当数组中有重复元素时我们需要找到最左边的目标值def left_bound(nums, target): 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 left if left len(nums) and nums[left] target else -1这个变种的关键在于当nums[mid] target时仍然继续向左搜索最终left指向的就是第一个等于target的位置3.2 寻找右边界类似地寻找最右边的目标值def right_bound(nums, target): 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 if right 0 and nums[right] target else -1注意这里当nums[mid] target时继续向右搜索最终right指向最后一个等于target的位置4. 旋转数组中的搜索问题4.1 无重复元素的旋转数组搜索def search_rotated(nums, target): left, right 0, len(nums) - 1 while left right: mid left (right - left) // 2 if nums[mid] target: return mid # 判断哪部分是有序的 if nums[left] nums[mid]: # 左半部分有序 if nums[left] target nums[mid]: right mid - 1 else: left mid 1 else: # 右半部分有序 if nums[mid] target nums[right]: left mid 1 else: right mid - 1 return -1这类问题的关键在于先确定哪一半是有序的检查目标是否在有序的那一半范围内根据结果调整搜索范围4.2 有重复元素的旋转数组搜索当数组包含重复元素时最坏情况会退化为O(n)def search_rotated_dup(nums, target): left, right 0, len(nums) - 1 while left right: mid left (right - left) // 2 if nums[mid] target: return True # 处理重复元素 if nums[left] nums[mid] nums[right]: left 1 right - 1 elif nums[left] nums[mid]: # 左半有序 if nums[left] target nums[mid]: right mid - 1 else: left mid 1 else: # 右半有序 if nums[mid] target nums[right]: left mid 1 else: right mid - 1 return False5. 二分答案类问题5.1 寻找峰值元素def find_peak_element(nums): left, right 0, len(nums) - 1 while left right: mid left (right - left) // 2 if nums[mid] nums[mid 1]: left mid 1 else: right mid return left这类问题的特点是不需要明确的目标值通过比较中间元素与其邻居来决定搜索方向最终收敛到峰值位置5.2 分割数组的最大值def split_array(nums, m): def can_split(max_sum): count 1 current 0 for num in nums: current num if current max_sum: count 1 current num if count m: return False return True left, right max(nums), sum(nums) while left right: mid left (right - left) // 2 if can_split(mid): right mid else: left mid 1 return left二分答案的通用模式确定搜索范围的下界和上界编写验证函数判断某个值是否可行根据验证结果调整搜索范围6. 常见错误与调试技巧6.1 死循环问题常见原因left和right更新不当如left mid而不是left mid 1循环条件使用while left right但更新方式不匹配调试方法打印每次循环的left,right,mid值手动模拟小测试用例的执行过程6.2 边界值错误常见情况数组为空时的处理目标值小于最小值或大于最大值重复元素的处理防御性编程建议先处理明显的边界情况在返回前检查索引是否越界6.3 整数溢出问题在计算mid时(left right) // 2可能在left和right很大时溢出。安全写法mid left (right - left) // 27. 实战题目解析7.1 搜索插入位置LeetCode 35def 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关键点标准二分的变种找不到时返回left即为应插入位置7.2 在排序数组中查找元素的第一个和最后一个位置LeetCode 34def searchRange(nums, target): def find_left(): 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 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() if left_pos len(nums) or nums[left_pos] ! target: return [-1, -1] return [left_pos, find_right()]这个解法使用两个辅助函数分别找左右边界最后检查找到的位置是否有效7.3 寻找旋转排序数组中的最小值LeetCode 153def findMin(nums): 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[right]比较来判断哪侧无序8. 进阶技巧与优化8.1 三分查找当函数是单峰或单谷时可以使用三分查找def ternary_search(f, left, right, eps1e-6): while right - left eps: m1 left (right - left) / 3 m2 right - (right - left) / 3 if f(m1) f(m2): right m2 else: left m1 return (left right) / 2适用场景求凸函数极值需要比二分更快的收敛速度8.2 二分答案的优化对于某些问题可以优化验证函数的时间复杂度。例如在分割数组的最大值问题中可以使用贪心算法来快速验证某个最大值是否可行。8.3 记忆化搜索与二分结合在某些动态规划问题中可以用二分来优化状态转移。例如最长递增子序列(LIS)的O(n log n)解法def lengthOfLIS(nums): tails [] for num in nums: idx bisect.bisect_left(tails, num) if idx len(tails): tails.append(num) else: tails[idx] num return len(tails)这个解法巧妙地使用二分查找来维护一个潜在的最长递增序列。