java 二分查找 方法 详解
Java中的二分查找是一种常用的搜索算法，用于在**有序集合（如数组或列表）**中快速查找目标值或其相关位置。Java提供了多种内置方法，同时也支持自定义实现。以下将详细解析二分查找的方法、实现及其应用场景。
1. Java中的二分查找方法
(1) Arrays.binarySearch (数组二分查找)
Arrays.binarySearch 是 Java 提供的内置二分查找方法，专用于 数组。
方法签名
// 对基础类型数组进行二分查找
public static int binarySearch(int[] a, int key)// 对引用类型数组进行二分查找
public static <T> int binarySearch(T[] a, T key, Comparator<? super T> c)
工作原理
- 适用于 升序排序 的数组。
- 返回结果：
- 如果找到目标值，返回目标值的索引。
- 如果未找到目标值，返回
-(插入点 + 1)，其中插入点是目标值应该插入的位置。
示例代码
import java.util.Arrays;public class BinarySearchExample {public static void main(String[] args) {// 基础类型数组int[] arr = {1, 3, 5, 7, 9};int target = 5;// 二分查找int result = Arrays.binarySearch(arr, target);System.out.println("目标值 " + target + " 的索引是：" + result);// 未找到目标值的情况target = 6;result = Arrays.binarySearch(arr, target);System.out.println("未找到目标值，返回值：" + result);}
}
输出结果
目标值 5 的索引是：2
未找到目标值，返回值：-4
注意事项
- 输入数组必须是升序排序。如果未排序，结果是未定义的。
- 对于基础类型数组，如
int[]、double[]等，使用默认的自然排序。 - 对引用类型数组（如
String[]），可以自定义比较器。
(2) Collections.binarySearch (集合二分查找)
Collections.binarySearch 是 Java 提供的另一个二分查找方法，专用于 列表。
方法签名
// 默认排序
public static <T extends Comparable<? super T>> int binarySearch(List<? extends T> list, T key)// 自定义排序
public static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c)
工作原理
- 适用于 升序排序 的列表（
List接口实现类，如ArrayList、LinkedList）。 - 返回结果与
Arrays.binarySearch相同：- 找到目标值，返回其索引。
- 未找到目标值，返回
-(插入点 + 1)。
示例代码
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;public class BinarySearchListExample {public static void main(String[] args) {// 创建升序排序的列表List<Integer> list = new ArrayList<>();list.add(1);list.add(3);list.add(5);list.add(7);list.add(9);// 默认排序二分查找int target = 5;int result = Collections.binarySearch(list, target);System.out.println("目标值 " + target + " 的索引是：" + result);// 自定义排序二分查找target = 6;result = Collections.binarySearch(list, target);System.out.println("未找到目标值，返回值：" + result);}
}
输出结果
目标值 5 的索引是：2
未找到目标值，返回值：-4
注意事项
- 输入列表必须是升序排序。
- 如果需要自定义排序，则必须提供一个
Comparator。
2. 自定义实现二分查找
除了使用内置方法，还可以根据需求自定义二分查找逻辑。以下是常见实现：
(1) 迭代实现
代码实现
public class CustomBinarySearch {public static int binarySearch(int[] arr, int target) {int left = 0, right = arr.length - 1;while (left <= right) {int mid = left + (right - left) / 2; // 避免溢出if (arr[mid] == target) {return mid; // 找到目标值} else if (arr[mid] < target) {left = mid + 1; // 搜索右半部分} else {right = mid - 1; // 搜索左半部分}}return -1; // 未找到目标值}public static void main(String[] args) {int[] arr = {1, 3, 5, 7, 9};int target = 7;int result = binarySearch(arr, target);if (result != -1) {System.out.println("目标值 " + target + " 的索引是：" + result);} else {System.out.println("目标值 " + target + " 不在数组中。");}}
}
输出结果
目标值 7 的索引是：3
(2) 递归实现
代码实现
public class RecursiveBinarySearch {public static int binarySearch(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 binarySearch(arr, target, mid + 1, right); // 搜索右半部分} else {return binarySearch(arr, target, left, mid - 1); // 搜索左半部分}}public static void main(String[] args) {int[] arr = {1, 3, 5, 7, 9};int target = 9;int result = binarySearch(arr, target, 0, arr.length - 1);if (result != -1) {System.out.println("目标值 " + target + " 的索引是：" + result);} else {System.out.println("目标值 " + target + " 不在数组中。");}}
}
输出结果
目标值 9 的索引是：4
3. 查找变种实现
(1) 查找插入位置
当目标值不存在时，返回它应该插入的位置。
代码实现
public class FindInsertPosition {public static int searchInsert(int[] arr, int target) {int left = 0, right = arr.length;while (left < right) {int mid = left + (right - left) / 2;if (arr[mid] < target) {left = mid + 1;} else {right = mid; // 收缩右边界}}return left; // 插入位置}public static void main(String[] args) {int[] arr = {1, 3, 5, 6};int target = 4;System.out.println("目标值的插入位置：" + searchInsert(arr, target));}
}
输出结果
目标值的插入位置：2
(2) 查找重复元素的第一个或最后一个位置
代码实现
public class FindFirstAndLast {public static int findFirst(int[] arr, int target) {int left = 0, right = arr.length - 1, result = -1;while (left <= right) {int mid = left + (right - left) / 2;if (arr[mid] == target) {result = mid; // 记录索引right = mid - 1; // 搜索左半部分} else if (arr[mid] < target) {left = mid + 1;} else {right = mid - 1;}}return result;}public static int findLast(int[] arr, int target) {int left = 0, right = arr.length - 1, result = -1;while (left <= right) {int mid = left + (right - left) / 2;if (arr[mid] == target) {result = mid; // 记录索引left = mid + 1; // 搜索右半} else if (arr[mid] < target) {left = mid + 1;} else {right = mid - 1;}}return result;}public static void main(String[] args) {int[] arr = {1, 2, 2, 2, 3, 4, 5};int target = 2;int first = findFirst(arr, target);int last = findLast(arr, target);System.out.println("目标值 " + target + " 的第一个位置：" + first);System.out.println("目标值 " + target + " 的最后一个位置：" + last);}
}
输出结果
目标值 2 的第一个位置：1
目标值 2 的最后一个位置：3
4. 二分查找的时间与空间复杂度
时间复杂度
- 时间复杂度：O(log n)
每次迭代将搜索范围缩小一半。
空间复杂度
- 空间复杂度：O(1) （迭代实现）
- 空间复杂度：O(log n) （递归实现，受限于递归栈的深度）
5. 二分查找的应用场景
典型场景
- 在有序数组中快速查找目标值。
- 寻找插入位置（如在动态更新数组中保持排序）。
- 解决查找范围问题（如查找第一个或最后一个满足条件的元素）。
- 算法优化：
- 二分查找可以用于复杂问题的优化（如搜索空间的最优值）。
- 如平方根计算、分配资源等问题。
注意事项
- 数组或列表必须是 有序的，否则二分查找的结果是未定义的。
- 对于查找第一个或最后一个满足条件的元素，需要结合搜索边界调整算法。
6. 总结
| 方法 | 场景 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
Arrays.binarySearch | 数组查找 | O(log n) | O(1) |
Collections.binarySearch | 列表查找 | O(log n) | O(1) |
| 自定义迭代实现 | 数组或列表查找 | O(log n) | O(1) |
| 自定义递归实现 | 数组或列表查找 | O(log n) | O(log n) |
| 查找插入位置 | 插入排序时保持有序 | O(log n) | O(1) |
| 查找重复元素的范围 | 统计元素出现的第一个或最后一个位置 | O(log n) | O(1) |
二分查找是高效的搜索算法，适合解决各种有序集合中的搜索问题。在使用前务必确保输入数据是有序的，并根据需求选择合适的实现方法。