二分查找以及序列的二段性

二分查找模板


  以下程序,需给定一个单调不下降整形数组A,整形变量lrv,程序保证返回值i落于闭区间 [l , , ,r] 中。

  假定 [l , , ,r] 中一定存在一个 i

  i满足A[i]i最小 (即序列A的左端点):return l;

  i满足A[i]i最大 (即vA中的前驱):

while (l < r) {
    int mid = l + r + 1 >> 1;
    if (A[mid] < v) l = mid; else r = mid - 1;
}
return l;

  i满足A[i]≤vi最小 (即序列A的左端点):return l;

  i满足A[i]≤vi最大 (即vv的前驱):

while (l < r) {
    int mid = l + r + 1 >> 1;
    if (A[mid] <= v) l = mid; else r = mid - 1;
}
return l;

  i满足A[i]>vi最小 (即vA中的后继):

while (l < r) {
    int mid = l + r >> 1;
    if (A[mid] > v) r = mid; else l = mid + 1;
}
return l;

  i满足A[i]>vi最大 (即序列A的右端点):return r;

  i满足A[i]≥vi最小 (即vv的后继):

while (l < r) {
    int mid = l + r >> 1;
    if (A[mid] >= v) r = mid; else l = mid + 1;
}
return l;

  i满足A[i]≥vi最大 (即序列A的右端点):return r;


可能的实现


#include 

template<class itr, class T>
itr lower_bound(itr first, itr last, const T &value){
    while (std::distance(first, last)) {
        itr mid = first;
        std::advance(mid, std::distance(first, last) / 2);
        if (*mid < value)
            first = ++mid;
        else last = mid;
    }
    return first;
}
#include 

template<class itr, class T>
itr upper_bound(itr first, itr last, const T &value){
    while (std::distance(first, last)) {
        itr mid = first;
        std::advance(mid, std::distance(first, last) / 2);
        if (!(value < *mid))
            first = ++mid;
        else last = mid;
    }
    return first;
}

Binary Search

  • 二分查找模板
  • 可能的实现
  • 二分查找
    • 问题引入
    • 各种变形


二分查找

Binary Search


  本文意在一举解决读者可能遇到的:

  1. 写出错误的二分查找
  2. 不知道如何使用二分查找

  等一系列与二分法相关的可能的问题。当然,笔者能力有限,如有不足,望海涵。


问题引入

leading-in


  给定长度为 n n n 的上升序列 A A A,即 A A A 中任意一对元素 a i , a j a_i,a_j ai,aj i < j i < j i<j 都满足 a i < a j a_i < a_j ai<aj,现在有 T T T 个询问,每个询问都会给出一个整数 b b b,你需要回答 b b b A A A 当中的位置,若 b ∉ A b \not\in A bA,则回答 − 1 -1 1


朴素查找


  对于第 t t t 次询问 b t b_t bt,我们可以顺序的取遍 A A A 中的每一个元素,直至第 i i i 个元素 a i = b t a_i = b_t ai=bt,此时,我们回答 i i i,若取至空都没找到等于 b t b_t bt 的元素,我们回答 − 1 -1 1

int search(int n, int *A, int b) {
    for (int i = 1; i <= n; ++i)
        if (A[i] == b) return i;
    return -1;
}

  因为问题没有保证 b b b 一定是在 A A A 中,也就是说,对于每一个询问,最差情况下我们会取遍 A A A,故完成所有询问的复杂度在 O ( T n ) O(Tn) O(Tn)

  这是个什么概念?

  在网络会所中,想要上网就得先进行实名认证,目前中国约有 14 14 14 亿人口, 10 10 10 万网吧,每个会所的客流量按较少的 500 500 500 来算,那么公安系统光网络会所一天的数据比对量可能就在 7 7 7 万万亿。

  打住,不能继续讲故事了,总之下面将实现二分查找,这是一种非常精妙的算法,更重要的是,它几乎随处可见,可以说只要你处在一个规模较大的系统中,一定的时间片段内,你就一定有在二分或有在“被二分”。


二分查找


  我们取 A A A 中的第 m i d = [ n 2 ] mid = [\frac n2] mid=[2n] [ ] [] [] 可以表示任意方向的取整函数,若 A A A 的第 m i d mid mid 个元素 a m i d = b a_{mid} = b amid=b,则我们可以直接回答 m i d mid mid

  否则,若 a m i d < b a_{mid} < b amid<b,我们会发现 1 ∼ m i d 1 \sim mid 1mid 之间的元素都小于 b b b,因为对于任意 i , j i,j i,j,都有 a i < a j a_i < a_j ai<aj,也就是任意小于于 m i d mid mid i i i,都满足 a i < a m i d a_i < a_{mid} ai<amid;同样的,若 a m i d > b a_{mid} > b amid>b,则表示 m i d ∼ n mid \sim n midn 之间的元素都大于 b b b。这两个区间内都再无存在 b b b 的可能性。

  于是,令 l e f t = 1 , r i g h t = n left = 1, right = n left=1,right=n,将在 1 ∼ n 1 \sim n 1n 之间的搜索看做在 l e f t ∼ r i g h t left \sim right leftright 之间的搜索,我们取 m i d = [ l e f t + r i g h t 2 ] mid = [\frac{left+right}2] mid=[2left+right],若 a m i d = b a_{mid} = b amid=b,我们直接回答 m i d mid mid,否则若 a m i d < b a_{mid} < b amid<b,令 l e f t = m i d + 1 left = mid + 1 left=mid+1,若 a m i d > b a_{mid} > b amid>b,令 r i g h t = m i d − 1 right = mid - 1 right=mid1,重复这一步直至区间长度为 0 0 0,此时回答 − 1 -1 1

int binary_search(int n, int *A, int b) {
    int left = 1, right = n;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (A[mid] == b) return mid;
        if (A[mid] < b) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

  递归实现的二分查找可以更便于有一定基础的读者去理解这个算法。

int binary_search(int left, int right, int *A, int b) {
    if (left > right) return -1;
    int mid = (left + right) / 2;
    if (A[mid] == b) return mid;
    if (A[mid] < b) return binary_search(mid + 1, right, A, b);
    return binary_search(left, mid - 1, A, b);
}

int binary_search(int n, int *A, int b) { return binary_search(1, n, A, b); }

  每一次查找都最少会使区间长度 l e n g t h length length 缩短 ⌊ l e n g t h 2 ⌋ \lfloor\frac {length}2\rfloor 2length,考虑最坏情况,即 b b b 并不在 A A A 中,设 f ( n ) f(n) f(n) 为长度为在 n n n 的上升序列上进行二分查找的最多次数,根据最坏情况我们有递推式 f ( n ) = f ( ⌊ n 2 ⌋ ) + 1 f(n) = f(\lfloor\frac n2\rfloor) + 1 f(n)=f(2n)+1

  当 n n n 2 2 2 的整次幂时, f ( n ) = f ( n 2 ) + 1 = f ( n 4 ) + 2 = ⋯ = f ( n n ) + log ⁡ 2 n = log ⁡ 2 n + 1 f(n) = f(\frac n2) + 1 =f(\frac n4) +2 =\cdots=f(\frac nn) +\log_2n =\log_2n + 1 f(n)=f(2n)+1=f(4n)+2==f(nn)+log2n=log2n+1

  而当 n n n 2 2 2 的整次幂时,我们将 l e n g t h length length 视为二进制串,则 l e n g t h length length 最坏的变化为 l e n g t h length length 最低位为 1 1 1 的情况,此时新的 l e n g t h ′ length' length l e n g t h length length 右移一位然后加 1 1 1,所以我们可以根据 l e n g t h length length 最高位是否会进位来判断在长度为 l e n g t h length length 的序列上进行二分查找所需要的次数。

  首先一个二进制串加 1 1 1,其意义为从二进制串从低到高按位取反,直至当前位为 0 0 0,取反后结束这个操作,比如 ( 1011 ) 2 + 1 = ( 1100 ) 2 (1011)_2+1 =(1100)_2 (1011)2+1=(1100)2 ( 1010 ) 2 + 1 = ( 1011 ) 2 (1010)_2+1 =(1011)_2 (1010)2+1=(1011)2。这是因为 2 2 2 进制数只能由 0 、 1 0、1 01 表示,而 a + 1 a+1 a+1 显然不等于 a a a,也就是某一位加 1 1 1 会且只能取反,而加法运算可以在进位结束时停止,故而这种现象对所有二进制串均成立,也就是说 l e n g t h length length 会使得最高位进位,当且仅当二进制表示下 l e n g t h length length 每一位均为 1 1 1,而进位后的 l e n g t h ′ length' length 2 2 2 的整次幂。

  自然有结论,对于任意长度为 n n n 的上升序列,二分查找的比较次数不会大于 ⌊ log ⁡ 2 n ⌋ + 1 \lfloor\log_2n\rfloor+1 log2n+1

  通常,我们认为二分查找的复杂度为 O ( log ⁡ n ) O(\log n) O(logn)


各种变形

parallel universes


  只有 10 % 10\% 10% 程序员能写对二分查找。

—— Jon Bentley  


  如果只是上文中的实现,真实的数据当然不会这么夸张,但我们真正遇到的问题很可能不会像最开始引入的问题那样标准,更具体地说,无法真正把握一些二分问题的细节,正是这 90 % 90\% 90% 程序员,使用二分查找时,无法得到预期效果的原因。

   c p p \mathrm{cpp} cpp 标准库定义了头文件 < a l g o r i t h m \mathrm{algorithm} algorithm>,里面包含了一组可用于多种数据结构,关于一个范围内的元素的操作的算法实现。

  当中使用二分查找实现了两个函数:itr lower_bound(first, last, value, pred)itr upper_bound(first, last, value, pred),其中itr表示某个元素的迭代器,它与firstlast的类型相同。

  first为要搜索范围中,第一个元素的迭代器。

  last为要搜索范围中,最后一个元素的下一个元素的迭代器。

  value为要返回的迭代器,指向的元素的值或要指向的元素超越的值。

  pred是一个比较器,若不指定比较器,默认使用<

  两个函数的使用前提是[first,last)间的元素单调不下降,lower_bound会返回第一个大于等于value的元素的迭代器,而upper_bound会返回第一个大于value的元素的迭代器。也就是说,同样的参数下,当[first,last)中没有元素值为value时,lower_boundupper_bound的返回值是相同的,而[first,last)间的元素若是都小于或都小于等于value,则会返回last

  从自然语言出发,lower_bound返回的是往[first,last)中插入value时,第一个不会破坏区间单调性的地址,而upper_bound返回的则是最后一个。

  考虑到部分读者没有接触过 c p p \mathrm{cpp} cpp 中,这部分的内容,下面给出两个方法在数组上的使用的简单案例:

#include 

const int n = 8;

int A[n], value;

int main() {
	init(); //初始化
    int* lower = std::lower_bound(&A[0], &A[n], value);
    int* upper = std::upper_bound(&A[0], &A[n], value);
}

  这两个函数可以准确完成几乎任何常用地有关二分查找的操作。

  仿照它的实现细节,我们可以将常用的二分查找分个类,

  闭区间[first,last]、左闭右开区间[first,last)上的二分。

  二分查找第一个>value≥value、最后一个≤value的元素的迭代器。


  回到序列A上,为了方便讨论,设我们要二分查找出下标落在闭区间[left,right]上,第一个≥value的元素的下标。

  由于下标落在闭区间,可能会出现找到的下标为right,但right指向的元素并不满足≥value的情况,但这目前不在我们的讨论范围之内,所以我们还要假设[left,right]中一定存在一个≥value的元素。

  令mid=(left+right)/2,若A[mid]≥value,则mid是一个可能的下标,[left,mid]是我们接下来要继续查找的区间,否则A[mid]mid一定不是可能的下标,则[mid+1,right]是我们接下来要继续查找的区间,所以我们可以先写出一个二分模板:

int binary_search(int left, int right, int *A, int value) {
    while (left < right) {
        int mid = (left + right) / 2;
        if (A[mid] >= value) right = mid;
        else left = mid + 1;
    }
    return left;
}

  从分治的角度来说,每次我们都会选择一个存在预期结果的子问题,left=right时停止,结果显然会会符合我们的预期,仿照上例模板,我们可以再编写二分查找下标落在闭区间[left,right]上,最后一个≤value的元素的下标的模板程序:

int binary_search(int left, int right, int *A, int value) {
    while (left < right) {
        int mid = (left + right) / 2;
        if (A[mid] <= value) left = mid;
        else right = mid - 1;
    }
    return left;
}

  可是实际应用,我们会发现很多场景下,第二个程序会进入死循环,这是因为,

  首先left一定是小于right的,则mid一定满足left≤mid,我们会发现,当mid=left时,我们进入到left=mid的分支,则区间范围接下来无论如何都不会缩小,故而进入死循环。

  为了能正确编写出二分,我们不妨假设k=right-left,则有k≥1mid=left+k/2,当k=1时,mid=left,这几个式子可以作证我们第一个程序的正确性,但我们目前要做的是解决第二程序的某个分支进入到死循环的问题,不妨再令mid向上取整,则此时mid=left+(k+1)/2,对于任意数据我们都有left≠mid,此时mid满足left,而当程序进入right=mid-1的分支,区间范围也会进一步缩小,直至left=right,此时二分结束。

  只需要一点小小的修改就够了。

int binary_search(int left, int right, int *A, int value) {
    while (left < right) {
        int mid = (left + right + 1) / 2;
        if (A[mid] <= value) left = mid;
        else right = mid - 1;
    }
    return left;
}

  同样是从分治的角度,对于二分区间[left,right],它的直接子问题只有两对情况:[left,mid][mid+1,right][left,mid-1][mid,right]

  第一种情况我们直接取mid=(left+right)/2,而第二种情况我们需要对mid向上取整。

  如果能较为透彻的理解上述内容,相信读者已经具备了能正确编写二分查找程序的能力。

  二分查找第一个>value、最后一个的元素的迭代器的程序,也能以类似的形式给出,接下来二分的大类还剩一种情况,即左闭右开区间[first,last) 上的二分。


  左闭右开区间上的二分,在整数域上,实质上还是闭区间[first,last-1]上的二分,只不过当vaule大于区间内所有元素时,通常我们会约定成俗的返回last

  容易发现,我们编写出的,查找第一个>value≥value的程序可以直接用于闭区间上的二分,因为只有当vaule大于区间内所有元素时,我们才会进入到[last,last)分支,此时返回last,其余情况与闭区间上二分相同。

  而查找最后一个≤value的元素,如若vaule大于等于区间内所有元素,则last-1正是我们要找的元素,其余情况与闭区间上二分相同。

  歇会