【数据结构 - 查找】(2)二分查找(折半查找)

【数据结构 - 查找】(2)二分查找(折半查找)

前言

该篇文章讲的是数据结构常用算法中的数据检索,二分查找(也称折半查找)。


一、概述

二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。

二分查找要求线性表必须采用顺序存储结构,并且表中元素是有序的。

二、查找过程

首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。

每次查找时都取中键值,然后比较,直至找出。


三、算法要求

  • 1.必须采用顺序存储结构。
  • 2.必须按关键字大小有序排列。

四、算法复杂度

折半查找法也称为二分查找法,它充分利用了元素间的次序关系,采用分治策略,可在最坏的情况下用O(log n)完成搜索任务。它的基本思想是:(这里假设数组元素呈升序排列)将n个元素分成个数大致相同的两半,取a[n/2]与欲查找的x作比较,如果x=a[n/2]则找到x,算法终止;如 果x<a[n/2],则我们只要在数组a的左半部继续搜索x;如果x>a[n/2],则我们只要在数组a的右 半部继续搜索x。

每次都是折中判断,算法时间复杂度最坏的情况下可以用 O(logn) 完成查找。


五、Java 二分查找

Java 二分查找代码,下面两个效果都一样的,只是考虑的边界不同。

我个人推荐使用第一个 while (start <= end) 的,因为 JDK 工具类Arrays.binarySearch()中也是用这个。看着也简单一点。

你变量 start 和 end 看不惯的话,可以换成 low 和 high。

    public static int binarySearch(int[] arr, int key) {
        int start = 0, end = arr.length-1;
        while (start <= end) {
            int mid = (start + end) >>> 2;
            if (arr[mid] == key) {
                return mid;
            } else if (arr[mid] > key) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        return -1;
    }
    public static int binarySearch(int[] arr, int key) {
        int start = 0, end = arr.length-1;
        while (start < end) {
            int mid = (start + end) / 2;
            if (arr[mid] == key) {
                return mid;
            } else if (arr[mid] > key) {
                end = mid;
            } else {
                start = mid + 1;
            }
        }
        return -1;
    }

六、Java 示例

这句计算中间下标可能更容易理解mid = start + (end - start) / 2。和这句是一样的 mid = (start + end) >>> 1。

请不要使用 mid = (low + high) / 2 ,因为他在极端情况下,两个数相加可能会导致溢出。

    public static void main(String[] args) {
        // 数据
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};

        // 二分查找
        int i = binarySearch(arr, 3);
        System.out.println(i); // 2
    }

    public static int binarySearch(int[] arr, int key) {
        // 第一个和最后一个下标
        int start = 0, end = arr.length - 1;
        while (start <= end) {
            int mid = start + (end - start) / 2; // 中间下标(请不要使用mid = (low + high) / 2,它极端情况下会溢出)
            // int mid = (start + end) >>> 1; // 同上 (无符号位右移>>>防止溢出)
            if (arr[mid] == key) {
                return mid;
            } else if (arr[mid] > key ) { // 中间值小于目标key
                end = mid - 1;
            } else { // 中间值大于目标key
                start = mid + 1;
            }
        }
        return -1;
    }

参考

百度百科:https://baike.baidu.com/item/%E7%BA%BF%E6%80%A7%E6%9F%A5%E6%89%BE/7814362