如何写一个正确的二分查找？

如何写一个正确的二分查找？
二分查找是一种高效的搜索算法，能够在有序数组中快速定位目标值。尽管其思想简单，但实际编写时容易因边界条件或细节错误导致bug。本文将介绍如何正确实现二分查找，帮助读者掌握这一基础却关键的算法技能。
**理解基本原理**
二分查找的核心是“分而治之”。通过不断将搜索范围减半，逐步逼近目标值。确保数组是有序的，这是二分查找的前提条件。算法通过比较中间元素与目标值，决定向左或向右继续搜索。理解这一过程是正确实现的基础。
**处理边界条件**
边界条件是二分查找中最容易出错的部分。例如，循环条件是`left <= right`还是`left < right`？中间值计算是否可能溢出？正确处理这些细节至关重要。通常，使用左闭右闭区间（`[left, right]`）更为直观，循环条件设为`left <= right`，确保所有元素都被检查。
**避免死循环**
死循环通常由更新左右边界的方式不当引起。例如，若中间值不满足条件时，错误地保留中间值会导致无限循环。正确的做法是：当目标值大于中间值时，更新`left = mid + 1`；反之，更新`right = mid - 1`。这样可以确保每次迭代范围都缩小。
**测试与验证**
编写完二分查找后，必须通过测试验证其正确性。测试用例应涵盖目标值在数组开头、中间、结尾、不存在以及数组为空等情况。例如，对数组`[1, 3, 5, 7]`，分别测试查找1、7、4和0，确保算法在各种情况下都能正确运行。
**优化与扩展**
掌握基础二分查找后，可以进一步学习其变种，如查找第一个或最后一个等于目标值的位置，或处理旋转有序数组等复杂场景。这些扩展问题在面试和实际应用中经常出现，深入理解二分查找的灵活性将大大提升解题能力。
通过以上几点，读者可以系统地掌握二分查找的正确实现方法。无论是初学者还是有经验的开发者，扎实的二分查找技能都是算法能力的基石。