当前位置：首页 > java >正文

【基础算法】二分查找算法 - JAVA

java 2025/5/2 7:30:33

一、算法概述

二分查找（Binary Search）是一种高效的查找算法，专门用于在已排序数组中查找特定元素。其核心思想是将查找区间反复折半，每次将目标值与区间中点元素比较，从而确定目标元素位于中点左侧还是右侧，直至找到目标元素或确定其不存在。二分查找的前提条件是数据必须有序排列且能够通过索引直接访问，常用于大规模数据的快速检索。

二、时间复杂度

二分查找的时间复杂度为 O(log n)，其中 n 是数组长度。每次比较操作将搜索范围减半，因此最多需要 log₂n 次比较即可确定元素位置。相比于线性查找 O(n) 的时间复杂度，二分查找在大规模数据处理时具有显著优势。二分查找的空间复杂度为 O(1)，因为它只需要常数额外空间来存储少量变量。

三、代码示例

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;// 找到目标值if (arr[mid] == target) {return mid;}// 目标在左半部分if (arr[mid] > target) {right = mid - 1;}// 目标在右半部分else {left = 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 BinarySearchFirst {public static int findFirstEqual(int[] arr, int target) {int left = 0;int right = arr.length - 1;int 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) {right = mid - 1;} else {left = mid + 1;}}return result;}public static void main(String[] args) {int[] arr = {1, 3, 5, 5, 5, 7, 9, 11};int target = 5;int result = findFirstEqual(arr, target);if (result != -1) {System.out.println("第一个等于 " + target + " 的元素索引位置: " + result);} else {System.out.println("元素 " + target + " 不在数组中");}}
}

3. 查找最后一个等于目标值的元素

public class BinarySearchLast {public static int findLastEqual(int[] arr, int target) {int left = 0;int right = arr.length - 1;int 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) {right = mid - 1;} else {left = mid + 1;}}return result;}public static void main(String[] args) {int[] arr = {1, 3, 5, 5, 5, 7, 9, 11};int target = 5;int result = findLastEqual(arr, target);if (result != -1) {System.out.println("最后一个等于 " + target + " 的元素索引位置: " + result);} else {System.out.println("元素 " + target + " 不在数组中");}}
}

4. 插值查找变种

public class InterpolationSearch {public static int interpolationSearch(int[] arr, int target) {int left = 0;int right = arr.length - 1;while (left <= right && target >= arr[left] && target <= arr[right]) {// 使用插值公式计算估计位置int pos = left + ((target - arr[left]) * (right - left)) / (arr[right] - arr[left]);if (arr[pos] == target) {return pos;}if (arr[pos] < target) {left = pos + 1;} else {right = pos - 1;}}return -1;}public static void main(String[] args) {int[] arr = {1, 3, 7, 12, 19, 25, 38, 50, 68, 90};int target = 25;int result = interpolationSearch(arr, target);if (result != -1) {System.out.println("使用插值查找，元素 " + target + " 在数组中的索引位置: " + result);} else {System.out.println("元素 " + target + " 不在数组中");}}
}

四、适用场景

有序数组的快速检索：当数据规模较大且已排序时，二分查找能大幅提高查询效率
查找边界值：如寻找数组中第一个或最后一个等于目标值的元素，或大于/小于目标值的第一个元素
实现高效插入：在有序数组中快速定位新元素的插入位置，以维持数组有序性
近似匹配：当精确匹配不存在时，可查找最接近目标值的元素
数据库索引：很多数据库系统的索引结构（如B树、B+树）依赖二分查找思想

五、局限性

⚠️ 要求数据有序：二分查找的前提是数据已排序，对于无序数据需先排序，增加前置成本
⚠️ 仅适用于顺序存储结构：如数组等能够通过索引直接访问的数据结构，不适用于链表
对动态变化的数据不友好：频繁插入删除的数据需要维护有序性，效率较低
内存要求较高：需要将整个数据集加载到内存，不适合处理超大规模数据

六、优化思路

避免整数溢出：计算中点时使用 mid = left + (right - left) / 2 而非 (left + right) / 2，防止大数据时整数溢出
插值查找优化：对于分布均匀的数据，可以使用插值查找公式，提高查找效率：
```
mid = min + (key - arr[min]) / (arr[max] - arr[min]) * (max - min)
```
这个优化在数据分布均匀的情况下，能够更快地接近目标位置。例如，在查找 [1,100] 中的 95，传统二分会先查找 50，而插值查找会直接尝试接近 95 的位置。
针对特定场景优化：针对重复元素、边界查找等特定场景进行算法调整
结合其他数据结构：如与跳表、哈希表等结合，构建更高效的混合查找策略
二分查找变体：根据具体需求，如旋转排序数组查找、峰值查找等场景，对算法进行变体设计

插值查找示例分析

以数组 [1, 3, 7, 12, 19, 25, 38, 50, 68, 90] 查找目标值 25 为例：

传统二分查找：首次中点为索引 4，值为 19，小于 25，向右查找；然后中点为索引 7，值为 50，大于 25，向左查找...
插值查找：首次估计位置计算：
```
pos = 0 + (25 - 1) * (9 - 0) / (90 - 1) ≈ 0 + 24 * 9 / 89 ≈ 0 + 24 * 0.101 ≈ 0 + 2.42 ≈ 2
```
虽然计算结果有误差（实际上第一次应该更接近 25 的位置），但仍然比传统二分查找更快接近目标。