c++二分查找详解_二分查找c++

二分查找的提出

一、问题的提出

有N个整数构成一个数组A，第i个整数是A[i]。

有Q个问题，第i个给出一个整数Xi，表示询问数组A是否包含Xi，包含就输出"yes"，否则输出"no"。

数据范围：

N<=100000

Q<=100000

对于60%的数据，0<=A[i], Xi<=1000000,。

对于100%的数据，0<=A[i], Xi<=10^9

二、问题的分析

1、对于每个询问，可以用for循环在A数组查找一遍，检查是否能找到。

这种算法，每一个询问，都需要查询O(N)次，总时间复杂度是(N*Q)。

2、对于60%的数据，可以用数组下标计数的方法，大致框架如下:

bool in[1000001];

int x, y;

for(int i=1; i<=N; i++) {

cin>>y;

in[y] = true; //数组下标对应的数标记为true

}

for(int i=1; i<=Q; i++){

cin>>x;

if(in[x] == true) cout<<"yes"<<endl;

else cout<<"no"<<endl;

}

三、二分查找的提出

第1个举例：N=10

A数组是：12 9 16 7 20 8 4 2 13 19

现在要询问A数组是否包含17。

步骤如下：

1、把A数组从小到大排序：2 4 7 8 9 12 13 16 19 20

2、开始二分查找的过程

令L=1， R=10， 表示我们用在A[1],A[2],...A[10]里面查找

如果询问的数小于A[1], 或者大于A[10]，那么肯定输出“no”

令mid = (L+R)/2 = (1+10)/2 =5, 我们检查A[mid] = A[5]的值：

因为要查找的数是17，大于A[5]，所以我们应该在A[5]至A[10]这一段查找，

所以把mid的值赋给L，即L = 5， R的值不变， R =10：

重新计算mid = (L+R)/2=(5+10)/2=7， A[mid] = A[7] = 13:

因为17大于A[7]，所以我们应该在A[7]至A[10]范围内查找17,

所以改变L的值，L = mid = 7, R = 10：

重新计算mid=(L+R)/2=(7+10)/2=8, A[mid] =A[8] = 16：

因为17大于A[8]，所谓我们要在A[8]至A[10]范围查找：

所以要改变L的值，L=8, R=10：

重新计算mid=(8+10)/2=(8+10)/2=9, A[mid] =A[9] = 19：

因为17小于A[9]，所以我们要在A[8]至A[9]范围查找，

所以要改变R的值， R = 9， L = 8：

由于此时只剩下两个数了，所以我们不再二分了，直接判断A[8]是否等于17,或者A[9]是否等于17即可。

也就是说： 当 L + 1 等于 R时，我们结束二分的过程。

第2个例子：N=5

A数组是： 10 3 9 6 2。

现在要查询A数组是否包含3。

把A数组从小到大排序：

令L=1， R=5,表示我们要在A[1]至A[5]范围内查找3。

开始二分查过的过程：

计算mid = (L+R)/2 = (1+5)/2 = 3：

因为我们要查找的数是3，小于A[mid]，所以我们下次要在A[L]至A[mid]范围内查找，

所以要设置 R=mid：

重新计算mid, mid = (L+R)/2 = (1+3)/2 = 2:

因为A[mid]等于3,说明A数组包含我们需要查找的数，所以输出“yes”

综合上面的第1和第2个例子，可以知道:

1、当要查找的数小于A[1]或者大于A[N]，返回"no"，否则进入二分查找过程

2、当A[mid]等于要查找的数，返回"yes", 否则继续二分查找。

3、当L+1等于R的时候，结束二分查找过程

4、如果A[L]或者A[R]等于要查找的数，返回"yes"，否则返回"no"

下面程序是二分查找的过程，请填空：

#include<bits/stdc++.h>

using namespace std;

int N, A[100005], Q;

bool cmp(int x, int y) {

return x < y;

}

string check(int x){

if(x<A[1] || x>A[N]) return "no";

int L = 1, R = N; //表示要在A[1]至A[N]范围查找x

for(; L+1<R; ){ //当查找范围超过2个数时继续二分查找，当范围只剩下两个数时结束二分查找

int mid = (L+R)/2; //先计算出[L,R]中间的那个数的下标

if(A[mid] == x) return "yes"; //如果中间那个数是我们要查找的数，返回yes

if(x>A[mid]) L = mid; //要查找的数大于A[mid]，所以要在右半部分查找

else R = mid; //要查找的数小于A[mid]，所以要在左半部分查找

}//结束二分查找，说明此时L+1等于R

if(A[L]==x || A[R]==x) return "yes";

else return "no";

}

int main(){

cin>>N;

for(int i=1;i<=N;i++) cin>>A[i];

sort(A+1,A+N+1,cmp); //对A数组进行从小到大的快速排序

cin>>Q; //共有Q个询问

for(int i=1; i<=Q; i++){

int x;

cin>>x;

cout<<check(x)<<endl;//查询数组A是否包含x

}

return 0;

}

二分查找的时间复杂度是

，本题目共有Q个询问，所以时间复杂度是：Q*LogN

二分查找应用1

【问题】

数组A有N个整数，分别是A[1]至A[N]，有Q个问题，第i个问题是给出Xi，表示询问数组A当中小于等于Xi的数有多少个。

1<=N,Q<=10^5。

【分析】

1、用两重循环肯定超时。

2、考虑二分查找。

3、把A数组用sort从小到大排序。

4、如果Xi < A[1]， 返回0

5、如果Xi >= A[N] , 返回N。

6、开始二分查找时，范围是这样的：

7、二分结束时，希望是这样的：

即： L+1 = R， 此时满足: A[1]至A[L]都是满足: <=Xi, 而A[R]至A[N]都满足: >Xi：

那么很显然，小于等于Xi的数共有L个。

8、为了达到上面最终的效果，那么在二分的过程中要如何处理呢？

(1) 根据当前的L和R，计算中间的那个数的下标mid = (L+R)/2,如果下图所示：

(2)如果 A[mid]<=Xi， 那么应该把mid赋值给L， L = mid:

(3)如果A[mid]>Xi，那么应该把mid赋值给R， R=mid:

(4)可以发现第(2)和第(3)点的条件非常重要，可以保证：A[1]至A[L]都是<=Xi， 而A[R]至A[N]都是>Xi。

下面程序是本题的解决方案，并填空

#include<bits/stdc++.h>

using namespace std;

int N, Q, A[100005];

bool cmp(int x, int y)

{

return x<y;

}

int find(int X)

{

if(X < A[1]) return 0; //边界条件

if(X >= A[N]) return N; //边界条件

int L=1, R=N; //

while(L+1<R) //二分过程始终保证A[1]至A[L]是<=X，A[R]至A[N]>X

{

int mid = (L+R)/2;

if( A[mid] <= X ) L = mid;

else R = mid;

}

return L; //因为始终保证A[1]至A[L]是<=X，A[R]至A[N]>X，而且此时L和R相邻

}

int main()

{

cin>>N;

for(int i=1;i<=N; i++) cin>>A[i];

sort(A+1,A+1+N,cmp); //快速排序

cin>>Q;

for(int i=1; i<=Q; i++) //有Q个询问

{

int X;

cin>>X;

cout<<find(x)<<endl;

}

return 0;

}