二分查找是一种高效的查找算法，其核心在于每次比较都排除一半的查找范围，从而快速定位目标值，但要求数据必须有序。实现方式有两种：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 循环。每次循环都计算中间位置 mid，然后根据 arr[mid] 与 target 的大小关系，调整 left 或 right 的值。mid = left + (right - left) / 2; 这种写法可以有效防止 (left + right) 溢出。
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 的使用正确。 -
手动模拟： 选取一些典型的测试用例，手动模拟二分查找的过程，观察
left、right和mid的变化。 -
使用断言： 在代码中加入断言，检查
left、right和mid的值是否符合预期。例如，可以断言left始终小于等于right。 - 编写单元测试： 编写充分的单元测试，覆盖各种边界情况，比如空数组、只有一个元素的数组、目标值在数组的开头或结尾等等。
例如，可以添加如下断言：
assert left <= right : "Left should be less than or equal to right";
通过这些调试技巧，可以有效地减少二分查找的错误。
