Java算法探秘：二分查找详解

当你需要在一个有序数组中查找特定元素时，二分查找是一种高效的算法。它的时间复杂度为 O(log n)，相较于线性查找的 O(n)，二分查找可以显著提高搜索效率。本文将详细解释什么是二分查找，以及如何在 Java 中实现它。

二分查找简介

二分查找，也称为折半查找，是一种在有序数组中查找目标元素的算法。它的原理是不断将查找范围减半，直到找到目标元素或确定目标元素不存在。二分查找的步骤如下：

1. 初始化左边界 left 为数组第一个元素的索引，右边界 right 为数组最后一个元素的索引。
2. 计算中间元素的索引 mid，它等于 (left + right) / 2。
3. 比较中间元素与目标元素：

• 如果中间元素等于目标元素，则找到目标，返回中间元素的索引。
• 如果中间元素大于目标元素，则将右边界更新为 mid - 1，继续在左半边查找。
• 如果中间元素小于目标元素，则将左边界更新为 mid + 1，继续在右半边查找。

4. 重复步骤 2 和 3，直到找到目标元素或左边界超过右边界。

Java 实现二分查找

以下是在 Java 中实现二分查找的示例代码：

/**
 * 二分查找
 */
public static int binarySearch(int[] intArr,int key){
    int left = 0;
    int right = intArr.length -1;

    while(left <= right){
        //计算中间元素的索引
        int mid = (left + right) >>> 1;
        //获取中间元素的值
        int midVal = intArr[mid];
        //比较中间元素和目标元素的值
        //如果中间元素小于目标元素，则将左边界更新为 mid + 1，继续在右半边查找。
        if (midVal < key)
            left = mid + 1;
        //如果中间元素大于目标元素，则将右边界更新为 mid - 1，继续在左半边查找。
        else if (midVal > key)
            right = mid - 1;
        //如果中间元素等于目标元素，则找到目标，返回中间元素的索引。
        else
            return mid;
    }

    //如果循环结束仍未找到目标元素，返回一个负数，表示未找到，通常为-(left + 1)
    return -(left + 1);
}

public static void main(String[] args) {

    int[] intArray = new int[]{2,4,5,7,9,11,16,23,45,67};

    System.out.println(binarySearch(intArray,5));
    System.out.println(binarySearch(intArray,23));
    System.out.println(binarySearch(intArray,1));
    System.out.println(binarySearch(intArray,20));
    System.out.println(binarySearch(intArray,110));

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

输出结果为：

2
7
-1
-8
-11
1
2
3
4
5

上述代码中，binarySearch 方法接受一个有序数组 intArr 和目标元素 key 作为参数，然后使用二分查找算法在数组中查找目标元素的索引。如果找到目标元素，返回它的索引；否则，返回 负数 表示目标元素不存在。

注意事项

二分查找的前提是数组必须是有序的，否则无法正常工作。如果数组不是有序的，需要先对数组进行排序，然后才能使用二分查找算法。

总结

二分查找是一种高效的查找算法，适用于有序数组。它的时间复杂度为 O(log n)，其中 n 是数组的长度。由于每次迭代都将搜索范围减半，因此它比线性查找等简单查找算法更加高效，特别是对于大型有序数组。通过仔细实现和理解二分查找算法，你可以在 Java 中轻松应用它来解决各种查找问题。