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; // 搜索右半