c++二分查找法

c++二分查找法

二分查找法是从区间[i，j]上连续不断将sum（a）·sum（b）<0的函数ans=sum（x），通过循环实现把函数sum（x）的0点所在区间一分为二，如此循环，使区间[i,j]的两个端点逐渐像0点靠近，得到0点近似值的方法。可以实现空间优化，适用于数据较大的题目。时间复杂第O（log（2n））。
在使用c++的二分查找法，要先将数据排序，二分查找法的基本思想可以这样总结：我们设数据是按升序排序的，根据题目中的数a，从序列的中间进行二分，如果当前i位置值等于a，则停止查找 ；假如a小于当前位置i，则在数列的前部分中查找；若a大于当前位置i，就在数列的后段进行查找，如果还没找到，再次二分，直到找到了a值。
二分例题：

小信的猜想
Description
有一天小信突发奇想，他有一个猜想，任意一个大于 2 的偶数好像总能写成 2 个质数的和。小信查了资料，发现这个猜想很早就被一个叫哥德巴赫的人提出来了，称为哥德巴赫猜想。目前还没有证明这个猜想的正确性。小信告诉你一个整数 n ，让你用这个数去验证。注意 1 不是质数。

Input

输入一个偶数 n(2<n≤8000000)。

Output

输出一个整数表示有多少对 (x,y) 满足 x+y=n(x≤y) 且 x,y 均为质数。

Sample Input 1
6
Sample Output 1
1
Sample Input 2
10
Sample Output 2
2
——摘自YCOJ
对，是一道哥德巴赫猜想。

#include<bits/stdc++.h>
using namespace std;
int a[9000000];
bool b[9000000];
int main(){int n,cnt=0,k=0;cin >> n;for(int i=2;i<n;i++){if(b[i]==0){for(int j=i+i;j<n;j+=i){b[j]=1;}a[k]=i;k++;}
}for(int i=0;i<k;i++){//查找 int tmp = n-a[i];int l=i,r=k-1,mid;while(r-l>1){mid=(l+r)/2;if(a[mid]<tmp){l=mid+1;}else{r=mid;}}if(a[l] == tmp || a[r]==tmp){cnt++;}}cout <&l