阅读:0       作者:严长生

二分查找(折半查找)算法(原理、实现及时间复杂度)

查找也是有特殊情况的,比如数列本身是有序的。这个有序数列是怎么产生的呢?有时它可能本身就是有序的,也有可能是我们通过之前所学的排序算法得到的。

不管怎么说,我们现在已经得到了有序数列了并需要查找。这时二分查找该出场了。

二分查找(Binary Search)也叫作折半查找二分查找有两个要求,一个是数列有序,另一个是数列使用顺序存储结构(比如数组)。

二分查找的原理及实现

二分查找的实现原理非常简单,首先要有一个有序的列表。但是如果没有,则该怎么办?可以使用排序算法进行排序。

以升序数列为例,比较一个元素与数列中的中间位置的元素的大小,如果比中间位置的元素大,则继续在后半部分的数列中进行二分查找;如果比中间位置的元素小,则在数列的前半部分进行比较;如果相等,则找到了元素的位置。每次比较的数列长度都会是之前数列的一半,直到找到相等元素的位置或者最终没有找到要找的元素。

我们先来想象一下,如果数列中有 3 个数,则先与第 2 个数进行比较,如果比第 2 个数大,则与第 2 个数右边的数列进行二分查找,这时这个数列就剩下一个数了,直接比较是否相等即可。所以在 3 个数的时候最多比较两次。

同理,在有 4 个数的时候,我们与中间数进行比较,一般中间数是首加末除以 2 算出来的,这时我们算出来的中间数是 (1+4)/2 等于 2,所以我们把要查找的数与第 2 个数比较,若比第 2 个数小,则直接与第 1 个数比较;否则与后面两个数进行二分查找,这时的中间数是 (3+4)/2 等于 3,也就是后半部分的第 1 个数。再接着进行比较,相等则找到相应的元素,小于则没有这个数(因为左边所有的数都已经判断过了),大于则继续向右查找。所以在 4 个数的时候最多比较 3 次。

以此类推,在 5 个数的时候最多查找 3 次,在 6 个数的时候也是最多查找 3 次。

下面我们以一个实际的例子来看看二分查找的操作过程。假设待查找数列为 1、3、5、7、9、11、19,我们要找的元素为 18,下面进行二分查找。首先待查数列如图 1 所示,我们找到中间的元素 7( (1+7)/2=4,第 4 个位置上的元素)。


图 1 在待查序列中找到中间元素

中间元素为 7,我们要找的元素比 7 大,于是在后半部分查找,现在后半部分数列为 9、11、19,我们找到中间元素,如图 2 所示。


图 2 在待查序列的后半部分找到中间元素

中间元素为 11,与 11 比较,比 11 大,则继续在后半部分查找,后半部分只有一个元素 19 了,这时直接与 19 比较,若不相等,则说明在数列中没有找到元素,结束查找。

对于这 7 个元素的数列,我们只查找并比较了 3 次,是不是比较次数很少呢?

下面我们来看看二分查找的实现。其实我们通过二分查找的操作步骤,可以很轻易地想出二分查找使用递归实现也很方便。下面我们用递归来实现二分查找。
public class BinarySearch {
    private int[] array;
    /**
     * 递归实现二分查找
     * @param target
     * @return
     */
    public int searchRecursion(int target) {
        if (array != null) {
            return searchRecursion(target, 0, array.length - 1);
        }
        return -1;
    }

    private int searchRecursion(int target, int start, int end) {
        if (start > end) {
            return -1;
        }
        int mid = start + (end - start) / 2;
        if (array[mid] == target) {
            return mid;
        } else if (target < array[mid]) {
            return searchRecursion(target, start, mid - 1);
        } else {
            return searchRecursion(target, mid + 1, end);
        }
    }
}
当然,除了递归实现,二分查找也可以使用非递归实现,代码如下:
public class BinarySearch {
    private int[] array;

    /**
     * 初始化数组
     * @param array
     */
    public BinarySearch(int[] array) {
        this.array = array;
    }

    /**
     * 二分查找
     * @param target
     * @return
     */
    public int search(int target) {
        if (array == null) {
            return -1;
        }

        int start = 0;
        int end = array.length - 1;

        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (array[mid] == target) {
                return mid;
            } else if (target < array[mid]) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        return -1;
    }
}
怎么样,是不是很简单?用测试小程序检查一下吧。
public class BinarySearchTest {
public static void main(String[] args) {
        int[] array = new int[]{1, 3, 5, 7, 9, 11, 19};
        BinarySearch binarySearch = new BinarySearch(array);
        System.out.println(binarySearch.search(0));
        System.out.println(binarySearch.search(11));
        System.out.println(binarySearch.searchRecursion(0));
        System.out.println(binarySearch.searchRecursion(11));
    }
}

二分查找的优化

这里我们考虑一下为什么是二分查找,而不是三分之一、四分之一查找。

发散一下思维,在查字典的时候,如果要查以a开头的单词,则你会怎么翻字典?肯定是从最前面开始翻;如果要查以 z 开头的单词,则应该会从最后开始翻。显而易见,你不会采用二分查找的方式去查这个单词在哪,因为这样你会很累。

同样,假设数据的范围是 1~10000,让你找 10,你会怎么样?简单来说,我觉得干脆用顺序查找好了,因为数列是升序的,没必要用二分查找,用顺序查找比二分查找的比较次数少。

所以经过这样的考虑,我们可以优化一下二分查找,并不一定要从正中间开始分,而是尽量找到一个更接近我们要找的那个数字的地方,这样能够减少很多查找次数。

之前我们都是根据长度去找到这个中间位置,现在是根据 key 所在的序列范围区间去找到这个位置。比如数列是 1~10,待查 key 是 3,我们可能会将大概前面三分之一的地方作为这个划分点。

不过还是有人给出了更精准的计算方式,即要查找的位置 P=low+(key-a[low])/(a[high]-a[low])×(high-low),这是有点复杂,但是仔细看一下,这种计算方式其实就是为了找 key 所在的相对位置,让 key 的值更接近划分的位置,从而减少比较次数。

这种对二分查找的优化其实有个名字,叫作插值查找,插值查找对于数列比较大并且比较均匀的数列来说,性能会好很多;但是如果数列极不均匀,则插值查找未必会比二分查找的性能好。

二分查找的特点及性能分析

二分查找的平均查找长度 ASL 为 ((n+1)log2(n+1))/n-1,有的书上写的是 log2(n+1)-1,或者是 log2n,具体计算比较麻烦,这里就不讨论了。

二分查找有个很重要的特点,就是不会查找数列的全部元素,而查找的数据量其实正好符合元素的对数,正常情况下每次查找的元素都在一半一半地减少。所以二分查找的时间复杂度为 O(log2n) 是毫无疑问的。当然,最好的情况是只查找一次就能找到,但是在最坏和一般情况下的确要比顺序查找好了很多。

二分查找的适用场景

二分查找要求数列本身有序,所以在选择的时候需要确认数列是否本身有序,如果无序,则还需要进行排序,确认这样的代价是否符合实际需求。

其实我们在获取一个列表的很多时候,可以直接使用数据库针对某个字段进行排序,在程序中需要找出某个值的元素时,就很适合使用二分查找了。

二分查找适合元素稍微多一些的数列,如果元素只有十几或者几十个,则其实可以直接使用顺序查找(当然,也有人在顺序查找外面用了一个或几个大循环,执行这几层大循环需要计算机执行百万、千万遍,没有考虑到机器的性能)。

一般对于一个有序列表,如果只需要对其进行一次排序,之后不再变化或者很少变化,则每次进行二分查找的效率就会很高;但是如果在一个有序列表中频繁地插入、删除数据,那么维护这个有序列表会让人很累,其实有更好的方案,别着急,我们慢慢想。