1、二分查找概念

二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。


2、二分查找简单实现

（1）左开右闭 【 ）

//非递归版本int*BinarySearch(int*a,intn,intkey){if(a==NULL||n==0){returnNULL;}//[)intleft=0;intright=n;while(left<right)//如果写成left<=right有可能越界{intmid=left+(right-left)/2;if(a[mid]>key){right=mid;//如果写成right=mid+1元素如果是a[0]=0，a[1]=1,要找1//left=0，right=1，mid=0//然后a[mid]<1,right=mid;此时找不到1，因为left<right//所以当为【）不要把未判断元素直接做right的下标}elseif(a[mid]<key){left=mid+1;}else{returna+mid;}}returnNULL;}voidtestBinary(){inta[10]={0,1,3,5,45,78,98,111,121,454};for(inti=9;i>=0;i--){int*temp=BinarySearch(a,10,i);if(temp==NULL){cout<<"NULL"<<endl;}elsecout<<*temp<<endl;}}//递归版本int*BinarySearch_R(int*a,intn,intkey,intleft,intright){if(a==NULL||n==0){returnNULL;}if(left<right){intmid=left+(right-left)/2;if(a[mid]>key){returnBinarySearch_R(a,n,key,left,mid);}elseif(a[mid]<key){returnBinarySearch_R(a,n,key,mid+1,right);}else{returna+mid;}}else{returnNULL;}}voidtestBinary_R(){inta[10]={0,1,3,5,45,78,98,111,121,454};for(inti=9;i>=0;i--){int*temp=BinarySearch_R(a,10,i,0,10);if(temp==NULL){cout<<"NULL"<<endl;}elsecout<<*temp<<endl;}}

（2）左闭右闭 【】

int*BinarySearch_C(int*a,intn,intkey){if(a==NULL||n==0){returnNULL;}//[]intleft=0;intright=n-1;while(left<=right){intmid=left+(right-left)/2;if(a[mid]>key){right=mid-1;//a[mid]的值已经判断过了}elseif(a[mid]<key){left=mid+1;//a[mid]已经判断过了}elsereturna+mid；}returnNULL;}voidtestBinary(){inta[10]={0,1,3,5,45,78,98,111,121,454};for(inti=9;i>=0;i--){int*temp=BinarySearch_C(a,10,i);if(temp==NULL){cout<<"NULL"<<endl;}elsecout<<*temp<<endl;}}//递归版本int*BinarySearch_CR(int*a,intn,intkey,intleft,intright){if(a==NULL||n==0){returnNULL;}if(left<=right){intmid=left+(right-left)/2;if(a[mid]>key){returnBinarySearch_R(a,n,key,left,mid-1);}elseif(a[mid]<key){returnBinarySearch_R(a,n,key,mid+1,right);}else{returna+mid;}}else{returnNULL;}}voidtestBinary_R(){inta[10]={0,1,3,5,45,78,98,111,121,454};for(inti=9;i>=0;i--){int*temp=BinarySearch_CR(a,10,i,0,9);if(temp==NULL){cout<<"NULL"<<endl;}elsecout<<*temp<<endl;}}

题目：

正整数数组a[0], a[1], a[2], ···, a[n-1]，n可以很大，大到1000000000以上，但是数组中每个数都不超过100。现在要你求所有数的和。假设这些数已经全部读入内存，因而不用考虑读取的时间。希望你用最快的方法得到答案。

提示：二分。