二分查找与数组操作实战：算法训练营核心技巧

1. 算法训练营开营：二分查找与数组操作实战

第一次参加算法训练营的学员往往会对数组基础操作感到既熟悉又陌生。熟悉是因为数组作为最基本的数据结构几乎出现在所有编程语言中，陌生则是因为在实际解题时总会出现各种边界条件问题。今天的三个题目——704二分查找、27移除元素和977有序数组的平方，恰好构成了数组操作的"铁三角"：查找、删除和转换。

我在刷题初期曾花费整整三天时间调试二分查找的边界条件，最终发现问题的根源在于对"循环不变量"的理解偏差。这种经历让我意识到，算法训练不能停留在AC（Accept）层面，更要理解每个判断条件背后的数学逻辑。下面我就结合这三个经典题目，分享如何建立正确的解题思维模式。

2. 704. 二分查找深度剖析

2.1 算法原理与边界陷阱

二分查找看似简单，但根据ACM统计，90%的程序员无法一次性写出完全正确的实现。核心难点在于处理区间定义和终止条件。我们以升序数组nums = [-1,0,3,5,9,12]和target=9为例：

def search(nums, target): left, right = 0, len(nums) - 1 # 定义闭区间[left, right] while left <= right: # 当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

关键点解析：

1. 区间定义决定边界处理：闭区间意味着right初始值为len(nums)-1
2. 循环条件left<=right保证最后剩余一个元素时仍能检查
3. mid计算使用left+(right-left)//2避免(left+right)可能导致的整数溢出

常见错误：将while条件写成left<right会导致漏查边界元素，特别是在查找首尾元素时

2.2 变种问题实战

二分查找有超过20种变种题型，训练营应该重点掌握以下三种：

1. 查找第一个等于target的元素：

while left <= right: mid = left + (right - left) // 2 if nums[mid] >= target: right = mid - 1 else: left = mid + 1 return left if nums[left] == target else -1

2. 查找最后一个等于target的元素：

while left <= right: mid = left + (right - left) // 2 if nums[mid] <= target: left = mid + 1 else: right = mid - 1 return right if nums[right] == target else -1

3. 查找第一个大于等于target的元素：

while left <= right: mid = left + (right - left) // 2 if nums[mid] >= target: right = mid - 1 else: left = mid + 1 return left

每种变种对应的判断条件和返回值都有微妙差异，建议在代码中用注释明确标注不变量的定义。

3. 27. 移除元素的双指针技法

3.1 暴力解法与优化空间

最直观的解法是发现目标值后，将后续所有元素前移：

def removeElement(nums, val): i = 0 n = len(nums) while i < n: if nums[i] == val: for j in range(i+1, n): nums[j-1] = nums[j] n -= 1 else: i += 1 return n

时间复杂度O(n²)在LeetCode上会超时，这引出了双指针的优化方案。

3.2 快慢指针的精妙配合

快指针扫描数组，慢指针标记有效位置：

def removeElement(nums, val): slow = 0 for fast in range(len(nums)): if nums[fast] != val: nums[slow] = nums[fast] slow += 1 return slow

这个实现有几个值得注意的细节：

1. 快指针fast总是比slow快一步或同步
2. 赋值操作nums[slow]=nums[fast]保证了原地修改
3. 最终slow的值就是新数组长度

实测技巧：当val出现频率低时，可以用交换代替赋值来减少写操作次数

4. 977. 有序数组的平方的三种解法

4.1 暴力排序法及其局限

最直接的方法是先平方后排序：

def sortedSquares(nums): return sorted(x*x for x in nums)

时间复杂度O(nlogn)虽然能通过，但未利用输入数组已排序的特性。

4.2 双指针的逆向思维

利用原数组有序的特性，最大值只可能出现在两端：

def sortedSquares(nums): n = len(nums) result = [0] * n left, right = 0, n - 1 for i in range(n-1, -1, -1): if abs(nums[left]) > abs(nums[right]): result[i] = nums[left] ** 2 left += 1 else: result[i] = nums[right] ** 2 right -= 1 return result

这个解法体现了几个重要思维：

1. 结果数组从后往前填充，避免额外空间交换
2. 比较绝对值而非实际值，处理负数情况
3. 时间复杂度优化到O(n)

4.3 边界条件测试用例

验证算法时需要特别考虑这些情况：

1. 全负数数组：[-4,-3,-2,-1]
2. 全正数数组：[1,2,3,4]
3. 零值数组：[0,0,0]
4. 混合数组：[-3,-1,0,2,5]

5. 算法训练的方法论建议

5.1 刷题三遍法实践

根据代码随想录推荐的方法，我改良出自己的三遍刷题法：

1. 第一遍：限时15分钟独立解题，记录初始思路
2. 第二遍：查看题解后重写，标注与优秀解法的差距
3. 第三遍：隔天后白板编程，重点训练边界条件处理

5.2 调试日志的重要性

在二分查找调试时，建议添加临时日志：

print(f"L={left}, R={right}, M={mid}, nums[M]={nums[mid]}")

这能清晰展示搜索区间变化过程，快速定位边界错误。

5.3 复杂度分析的实操技巧

不要死记公式，建议：

1. 根据循环结构直观判断：单层循环通常是O(n)
2. 嵌套循环看乘积关系：双重循环可能是O(n²)
3. 递归算法画调用树：深度乘以每层操作数

6. 常见错误与调试实录

6.1 二分查找的死循环陷阱

当出现死循环时，检查三个关键点：

1. 区间更新是否至少缩小1（mid±1）
2. 循环条件是否允许left==right的情况
3. mid计算是否可能陷入无限取整

6.2 数组索引越界防护

在操作数组时务必进行前置检查：

if not nums: return 0 if index >= len(nums): raise IndexError

6.3 双指针的同步问题

快慢指针类题目常见错误模式：

1. 指针移动条件错误（该移动时未移动）
2. 指针初始位置不当（应从同一起点开始）
3. 终止条件遗漏边界情况

7. 性能优化与测试策略

7.1 LeetCode提交时的优化技巧

1. 在函数开始处添加极端条件判断
2. 使用内置函数替代手动循环（如max()）
3. 避免不必要的临时变量创建

7.2 自定义测试用例设计

建议按以下比例构造测试集：

1. 30%常规情况
2. 30%边界条件
3. 20%极端案例
4. 20%随机生成

例如对移除元素题目，应该包含：

• 空数组
• 全部元素都需要移除
• 首尾元素需要移除
• 连续多个需要移除的元素

8. 从这三个题目看算法思维

这三个题目虽然简单，但蕴含了算法设计的核心思想：

1. 二分查找体现分治思想
2. 双指针展示如何优化多重循环
3. 平方排序题演示了问题转化的技巧

我在面试候选人时，发现能清晰解释这三个题目背后思维逻辑的开发者，通常具有更扎实的算法基础。建议在训练营期间，每个题目都尝试用不同方法实现，并比较它们的优劣。