数据结构与算法之一搜索算法

发表于 阅读次数： 评论数： 本文字数： 832 阅读时长 ≈ 1 分钟

二分查找

二分查找的介绍

二分查找（Binary Search）也称折半查找，它是一种效率较高的查找算法。特别注意，二分查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

二分查找的优点

  • 高效性： 二分查找算法的时间复杂度为 O (log n)，其中 n 是要搜索的元素数量。相对于线性搜索算法的 O (n) 时间复杂度，二分查找算法通常更快。
  • 适用范围广： 二分查找算法适用于有序数组或列表。只要数据结构能够支持随机访问并且有序，就可以使用二分查找。
  • 简单清晰： 二分查找算法的实现相对简单，易于理解和实现。

二分查找的缺点

  • 要求有序： 二分查找算法要求数据结构是有序的，如果数据无序，则需要先进行排序，这会增加额外的时间复杂度。
  • 不适用于动态数据结构： 如果数据结构经常变化，例如频繁地插入或删除元素，那么维护数据结构的有序性将变得非常昂贵，使得二分查找算法不再适用。
  • 只能用于一部分数据结构： 二分查找算法只适用于支持随机访问的数据结构，例如数组或随机访问列表。对于链表等不支持随机访问的数据结构，二分查找算法无法直接应用。

二分查找的原理

存在这样的一个数组 int[] arr = {11, 22, 33, 44, 55, 66, 77}，假设需要查找的目标值是 66。

定义一个 left 和 right 变量，对应的就是数组的索引 0 和索引 arr.length - 1。

通过 (left + right) / 2 折半计算，得到 mid = 3，此时 arr[mid] 的值为 44，并不是要查找的 66，通过比较 44 是比 66 小的，就会进入下一轮的二分查找。

由于上一步得到 arr[mid] 的值小于目标值 66，为了缩小查找范围，需要把 left 索引移到中间索引的右边，而 right 索引则保持不变，此时原本索引 0 - 6 的范围瞬间缩小到了 4 - 6，距离目标值 66 也越来越近。

再次进行 (left + right) / 2 折半计算，得到 mid = 5，发现 arr[mid] 的值刚好等于目标值 66，说明目标值已经被找到。

二分查找的实现

  • 基础版本的写法
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
public class BinarySearchDemo {

    /**
     * 二分查找
     *
     * @param array  有序数组
     * @param target 目标值
     * @return 目标值的下标，查找不到则返回 -1
     */
    public static int binarySearch(int[] array, int target) {
        int left = 0;  // 左边位置
        int middle = 0;  // 中间位置
        int right = array.length - 1;  // 右边位置

        while (left <= right) {
            middle = (left + right) / 2;
            if (array[middle] == target) {
                // 找到目标值
                return middle;
            } else if (array[middle] < target) {
                // 目标值在数组的右侧
                left = middle + 1;
            } else {
                // 目标值在数组的左侧
                right = middle - 1;
            }
        }

        return -1;
    }

}
  • 优化版本的写法
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
public class BinarySearchDemo {

    /**
     * 二分查找
     *
     * @param array  有序数组
     * @param target 目标值
     * @return 目标值的下标，查找不到则返回 -1
     */
    public static int binarySearch(int[] array, int target) {
        int left = 0;  // 左边位置
        int middle = 0;  // 中间位置
        int right = array.length - 1;  // 右边位置

        while (left <= right) {
            middle = left + (right - left) / 2;
            if (array[middle] == target) {
                // 找到目标值
                return middle;
            } else if (array[middle] < target) {
                // 目标值在数组的右侧
                left = middle + 1;
            } else {
                // 目标值在数组的左侧
                right = middle - 1;
            }
        }

        return -1;
    }

}