正儿八经的二分查找模板 调用函数 让你更明白

解题思路二分查找

注意事项:简单的二分 中间加一个判断 大于这个中间数 小于后面一个数:

参考代码:

#include<bits/stdc++.h>

using namespace std;

//防止数过大 都开的long long 

long long a[100000];

//传数组 左边值l 一般为0 右边值r为长度-1 tar为目标数 

//下面这个为标准的二分查找 

/*long long f1(long long a[],long long l,long long r,long long tar)

{

while(l <= r)

{

long long mid = (l+r)/2;

if(a[mid] == tar) return mid;

if(a[mid] < tar) l = mid+1;

if(a[mid] > tar) r = mid-1;

}

}*/

long long f1(long long a[],long long l,long long r,long long tar)

{

while(l <= r)

{

long long mid = (l+r)/2;

//这个查最近的值  则加一个 判断 正好大于mid中间这个数 并且小于后面一个数就行 

if(a[mid] == tar || a[mid] < tar && a[mid+1] > tar) return mid; //return的为下标 

if(a[mid] < tar) l = mid+1;

if(a[mid] > tar) r = mid-1;

}

}

int main()

{

long long m,n,k,i,j;

cin >> m;

for(i = 0; i < m;i++)

cin >> a[i];

sort(a,a+m);//简单排序 

cin >> n;

while(n--)

{

cin >> k;

if(k >= a[m-1])//如果大于最大的 肯定输出最后一个 

{

cout << a[m-1]<<endl;

continue;

}

if(k <= a[0])//小于最小的 肯定输出第一个 

{

cout << a[0] << endl;

continue;

}

int lp = f1(a,0,m-1,k);//lp接收传回来的下标 

if(a[lp] == k)//等于 输出 

cout << k << endl;

else if(k - a[lp] > a[lp+1] - k)//这个判断 该数与前后哪一个数离的近 

cout << a[lp+1] << endl;

else cout << a[lp]<<endl;

}

return 0;

}