二分查找（Binary Search）是一种高效的查找算法，适用于有序数组。通过每次将查找范围缩小一半，能够快速找到目标值或确定目标值不存在。相比线性查找（O(n)），二分查找的时间复杂度为 O(log n)，效率更高。
一、二分查找的原理
二分查找又叫折半查找，基本原理是“分而治之”的思想：每次将查找范围减半，从而大大减少比较的次数。它要求数据必须有序，因为算法利用了数据的排序信息来决定目标值可能出现在哪一半。
详细的工作流程：
- 初始化边界：我们首先设定查找的范围，
low指向数组的起始位置，high指向数组的末尾位置。 - 计算中间点：通过
mid = (low + high) / 2计算当前查找范围的中间点mid。 - 比较中间值与目标值：
- 如果
arr[mid] == target，那么就找到了目标值，直接返回mid。 - 如果
arr[mid] > target，目标值一定在左半部分，将high更新为mid - 1。 - 如果
arr[mid] < target，目标值一定在右半部分，将low更新为mid + 1。
- 如果
- 重复步骤 2 和 3：在每一步中，查找范围缩小一半，直到
low超过high，这时可以确定数组中没有目标值。 - 终止条件：当
low > high时，查找范围已经为空，意味着目标值不存在。
这个过程可以用递归或循环实现。在每次查找中，二分查找算法都会排除一半的元素，因此查找效率非常高。
二、二分查找的时间复杂度
1. 时间复杂度 O(log n)：
- 在每一次迭代或递归中，查找的范围都会缩小一半，因此执行的步骤数是
log n（以 2 为底的对数），其中 n 是数组的长度。 - 假设数组的长度为 16，第一次比较后，范围从 16 减少到 8，接着是 4，再到 2，最后是 1，因此总共需要 4 次比较，正好是
log2(16)。
2. 空间复杂度 O(1)（循环实现）或 O(log n)（递归实现）：
- 循环版本只使用了几个额外的变量（
low、high、mid），因此空间复杂度是常数 O(1)。 - 递归版本则每次递归调用都会增加栈空间，递归的深度是 O(log n)，所以空间复杂度是 O(log n)。
三、二分查找的伪代码
二分查找可以通过递归或循环两种方式实现，下面是伪代码版本的二分查找。
循环实现的伪代码：
public static int binarySearch(int[] arr, int target) {int low = 0; // 起始指针int high = arr.length - 1; // 结束指针// 当 low <= high 时，继续查找while (low <= high) {// 计算中间位置，防止溢出int mid = low + (high - low) / 2;// 找到目标值if (arr[mid] == target) {return mid;}// 如果目标值在右半部分else if (arr[mid] < target) {low = mid + 1;}// 如果目标值在左半部分else {high = mid - 1;}}// 目标值不在数组中，返回 -1return -1;}
递归实现的伪代码：
/*** 使用二分查找算法递归地在一个排序的整数数组中查找目标值。** @param arr 排序的整数数组* @param low 搜索范围的最低索引* @param high 搜索范围的最高索引* @param target 目标值，要查找的整数* @return 找到的目标值的索引，如果目标值不存在则返回-1*/public static int binarySearchRecursive(int[] arr, int low, int high, int target) {// 当low大于high时，表示搜索范围为空，返回-1表示目标值不存在if (low > high) {return -1; // 目标值不存在}// 计算中间位置的索引，避免大数组可能导致的整型溢出int mid = low + (high - low) / 2;// 如果中间位置的元素等于目标值，直接返回其索引if (arr[mid] == target) {return mid; // 找到目标，返回索引}// 如果中间位置的元素小于目标值，在右半部分继续查找else if (arr[mid] < target) {return binarySearchRecursive(arr, mid + 1, high, target); // 右半部分继续查找}// 如果中间位置的元素大于目标值，在左半部分继续查找else {return binarySearchRecursive(arr, low, mid - 1, target); // 左半部分继续查找}}
四、二分查找的代码实现
1. 循环版本：
public class BinarySearch {public static int binarySearch(int[] arr, int target) {int low = 0;int high = arr.length - 1;while (low <= high) {int mid = low + (high - low) / 2; // 防止溢出if (arr[mid] == target) {return mid; // 找到目标，返回索引} else if (arr[mid] < target) {low = mid + 1; // 在右半部分继续查找} else {high = mid - 1; // 在左半部分继续查找}}return -1; // 目标值不存在}public static void main(String[] args) {int[] arr = {1, 3, 5, 7, 9, 11, 13, 15};int target = 7;int result = binarySearch(arr, target);if (result != -1) {System.out.println("目标值 " + target + " 的索引为: " + result);} else {System.out.println("目标值 " + target + " 不存在");}}
}
2. 递归版本：
public class BinarySearchRecursive {public static int binarySearchRecursive(int[] arr, int low, int high, int target) {if (low > high) {return -1; // 目标值不存在}int mid = low + (high - low) / 2;if (arr[mid] == target) {return mid; // 找到目标，返回索引} else if (arr[mid] < target) {return binarySearchRecursive(arr, mid + 1, high, target); // 右半部分继续查找} else {return binarySearchRecursive(arr, low, mid - 1, target); // 左半部分继续查找}}public static void main(String[] args) {int[] arr = {1, 3, 5, 7, 9, 11, 13, 15};int target = 7;int result = binarySearchRecursive(arr, 0, arr.length - 1, target);if (result != -1) {System.out.println("目标值 " + target + " 的索引为: " + result);} else {System.out.println("目标值 " + target + " 不存在");}}
}
五、二分查找的注意事项
- 数组必须是有序的：二分查找只适用于有序数组。如果数组未排序，则必须先排序才能使用二分查找。
- 边界条件：需要仔细处理
low、high的更新。特别是在循环和递归时，确保范围的更新不出错。 - 整数溢出问题：在计算
mid时，直接使用(low + high) / 2可能会导致整数溢出，因此推荐使用low + (high - low) / 2这种安全的写法。
六、二分查找的变种
- 查找第一个等于目标值的元素：在有重复元素的情况下，查找第一个等于目标值的元素。
- 查找最后一个等于目标值的元素：在有重复元素的情况下，查找最后一个等于目标值的元素。
- 查找第一个大于等于目标值的元素：在有序数组中查找第一个大于或等于目标值的元素。
- 查找最后一个小于等于目标值的元素：在有序数组中查找最后一个小于或等于目标值的元素。
七、应用场景
- 有序数据的快速查找：二分查找广泛用于查找有序数据中的目标值，比如数据库索引查找。
- 算法题目：二分查找在很多算法题中出现，特别是涉及到查找问题的优化时，比如查找旋转数组中的最小值、找峰值等。
- 查找临界值：二分查找也可以用于优化问题，查找某种操作的最优解，比如在一些最小化或最大化问题中通过二分查找进行边界值查找。
二分查找是一种非常高效的查找算法，在有序数据中有广泛应用，其思想简单但实用。