脑补一个非有序数组的二分查找算法

原本想写Base64算法的,不过我还是想写点有趣的,而不是Base64这样没有什么思维难度的模版。在手贱在hihoCoder上看到了一个关于非有序数组的二分查找的题目,要求在非有序的数组上做线性的查找(于是就不能排序了),找到这个数组中第K大的值。做了一个下午,到晚上搞定,终于抠完几个细节。不过想的过程还是蛮棒的,这个算法是从快速排序衍生而来的,而从经典算法出发去yy,能让我们思考更多经典算法的细节,感受经典算法的那种美。

快速排序

在讲这个二分查找算法的之前我们还是先看看它的基础:快速排序算法。虽然快速排序有很多缺点:它不稳定、难理解、会被奇葩数据拿去卡,但在实践当中还是个很快很靠谱的排序算法,比Java和Python所采用的TimSort不知道高到哪里去了。我觉得作为一个IT从业者,不能理解快排就好像一个中国人没读过《论语》一样。
讲解快排的文章有很多,任何一本算法书也都不可能不讲快排。不过我这里需要特别阐述一下快排究竟在干什么。
基本的观点是,每一“趟”的快排是针对原来数据的一个区间上进行的。首先在这个区间上随意取一个值mid,然后遍历一遍这个区间,使得能够把所有数据中小于等于mid的扔到区间的左部分,大于等于mid的扔到区间的右部分。然后左右分别继续搞。这么说太抽象了,我们拿几个数据玩玩看:

假设初始的数据是34 10 23 78 56,那么如果我们取第一个34为mid,我们就要遍历一遍数组(在O(n)的时间内)变成10、23、34在左边,56、78在右边。至于10、23、34它们之间的顺序则无关紧要,不论是10、23、34还是23、34、10还是34、10、23还是别的什么都不管,反正前三个都是小于等于34的,后两个都是大于等于34的。

其实34也可能在后面一半。这点非常重要,因为这就意味着mid的值位置是不确定的,如果数据中有多个mid,它可能左右两部都有分布。实际上一趟快排结束后,我们只能保证小于mid的在左边,大于mid的在右边,至于mid在哪?不知道。

现在我放一段我的快排实现。我取mid一般是取中间那个位置,正常情况下是要随机取,而算法讲解的时候一般取第一个。

void Qsort(int l,int r){
    int mid=A[(l+r)/2];
    do{
        while (A[i]<mid) i++;
        while (A[j]>mid) j--;
        if (i<=j){
            int k=A[i];
            A[i]=A[j];
            A[j]=k;
            i++;j--;
        }
    }while (i<=j);
    if (l<j) Qsort(l,j);
    if (i<r) Qsort(i,r);
}

这段程序能保证的是,所有小于mid的都在l~j范围内,而所有大于mid的都在i到r范围内。同时j+1到i-1范围内的(至多一个,可能是零个),一定是mid。但是所有是mid的值,位置是不确定的。

非有序数组的线性查找算法

我们现在可以开始想怎么在非有序的数组里,避免全部排序整个数组,而找到某个数是第几大了。由快速排序的算法的思想出发,我们可以发现,如果一趟快排结束,那么我们每次能把小于mid的扔到区间左边,大于mid的扔到区间右边,平均来看,查找范围就缩小了一半。(当然被卡是可能的,我们只是寻求一个期望复杂度的较优。)这样一个算法能够实现,那么整体复杂度就是
算法复杂度估计

要注意的是i与j之间的差。在上述的快排程序跑过一趟之后,j<i,但是我们并不确定j和i中间是否会有一个数。这个数可能有,也可能没有,必须特殊判断。最后写出来的线性查找算法如下:

int Search(int l,int r){
    if (l==r) return A[l];
    int i=l,j=r;
    int mid=A[(l+r)>>1];
    do{
        while (A[i]<mid) i++;
        while (A[j]>mid) j--;
        if (i<=j){
            int k=A[i];
            A[i]=A[j];
            A[j]=k;
            i++;j--;
        }
    }while (i<=j);
    if (j==i-2){
        if (j+1==K) return A[j+1];
    }
    if (K<=j) return Search(l,j);
    if (K>=i) return Search (i,r);
}

我拿了一个用algorithm库提供的sort函数做的O(NlogN)排序程序做对拍,在N=106的情况下,不开O2速度快一倍,开了O2快30%左右,效率提升还是很显著的。

Published by

sweetdum

某个退役的OIer,热爱数学和哲学,就读于上海另一所大学的码农生。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>