二分查找是一种高效的查找算法，其核心在于每次比较都排除一半的查找范围，从而快速定位目标值，但要求数据必须有序。实现方式有两种：1. 循环实现通过 while(left
二分查找，也叫折半查找，是一种高效的查找算法。它的核心在于每次比较都排除掉一半的查找范围，从而快速定位目标值。关键在于数据必须是有序的。
二分查找的Java实现，就是利用循环或者递归，不断缩小搜索范围，直到找到目标值或者确定目标值不存在。
解决方案
立即学习“Java免费学习笔记（深入）”；
二分查找的实现方式有两种：循环和递归。这里分别给出示例代码。
1. 循环实现
public class BinarySearch { public static int binarySearch(int[] arr, int target) { int left = 0; int right = arr.length - 1; while (left <= right) { int mid = left + (right - left) / 2; // 防止 (left + right) 溢出 if (arr[mid] == target) { return mid; // 找到目标值，返回索引 } else if (arr[mid] < target) { left = mid + 1; // 目标值在右半部分，更新左边界 } else { right = mid - 1; // 目标值在左半部分，更新右边界 } } return -1; // 没有找到目标值，返回 -1 } public static void main(String[] args) { int[] arr = {2, 5, 7, 8, 11, 12}; int target = 13; int index = binarySearch(arr, target); if (index == -1) { System.out.println("Element is not found!"); } else { System.out.println("Element is found at index: " + index); } } }
这段代码的核心是 while (left
2. 递归实现
public class BinarySearchRecursive { public static int binarySearchRecursive(int[] arr, int target, int left, int right) { if (left > right) { return -1; // 没有找到目标值 } int mid = left + (right - left) / 2; if (arr[mid] == target) { return mid; } else if (arr[mid] < target) { return binarySearchRecursive(arr, target, mid + 1, right); // 在右半部分递归查找 } else { return binarySearchRecursive(arr, target, left, mid - 1); // 在左半部分递归查找 } } public static void main(String[] args) { int[] arr = {2, 5, 7, 8, 11, 12}; int target = 13; int index = binarySearchRecursive(arr, target, 0, arr.length - 1); if (index == -1) { System.out.println("Element is not found!"); } else { System.out.println("Element is found at index: " + index); } } }
递归实现的核心在于 binarySearchRecursive 方法的自身调用。每次调用都传入新的 left 和 right 值，缩小查找范围。
二分查找的时间复杂度是 O(log n)，非常高效。但前提是数组必须是有序的。如果数组无序，需要先排序，排序的时间复杂度通常是 O(n log n)。
二分查找有哪些常见的变体？
二分查找的变体主要体现在对边界条件的处理上。比如，查找第一个大于等于目标值的元素、查找最后一个小于等于目标值的元素等等。这些变体都需要对循环条件和边界条件进行细致的调整。
以查找第一个大于等于目标值的元素为例，代码如下：
public static int binarySearchFirstGreaterOrEqual(int[] arr, int target) { int left = 0; int right = arr.length - 1; int index = -1; while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] >= target) { index = mid; right = mid - 1; // 继续在左半部分查找 } else { left = mid + 1; // 在右半部分查找 } } return index; }
关键在于 arr[mid] >= target 时，不仅要记录 mid，还要继续在左半部分查找，直到找到第一个大于等于目标值的元素。
二分查找在实际应用中有哪些场景？
二分查找广泛应用于各种需要快速查找的场景，比如：
- 有序数组查找： 这是最直接的应用。
- 在排序数组中查找特定范围的元素： 可以结合二分查找的变体实现。
- 数值逼近： 比如求一个数的平方根，可以通过二分查找不断逼近。
- 在某些游戏或算法中进行决策： 比如猜数字游戏，或者在一些搜索算法中进行剪枝。
另外，数据库索引的实现也经常用到二分查找的思想。
二分查找的边界条件容易出错，有什么好的调试技巧？
二分查找的边界条件确实容易出错。调试时，可以采用以下技巧：
- 仔细检查循环条件： 确保循环条件 left
- 手动模拟： 选取一些典型的测试用例，手动模拟二分查找的过程，观察 left、right 和 mid 的变化。
- 使用断言： 在代码中加入断言，检查 left、right 和 mid 的值是否符合预期。例如，可以断言 left 始终小于等于 right。
- 编写单元测试： 编写充分的单元测试，覆盖各种边界情况，比如空数组、只有一个元素的数组、目标值在数组的开头或结尾等等。
例如，可以添加如下断言：
assert left <= right : "Left should be less than or equal to right";
通过这些调试技巧，可以有效地减少二分查找的错误。
