1、二分查找概念
二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
2、二分查找简单实现
（1）左开右闭 【 ）
计算
安全
数据库
网络和加速
企业服务
//非递归版本
int* BinarySearch(int *a,int n,int key)
{
if (a==NULL||n==0)
{
return NULL;
}
//[)
int left=0;
int right=n;
while(left<right) //如果写成left<=right 有可能越界
{
int mid=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的下标
}
else if(a[mid]<key)
{
left=mid+1;
}
else
{
return a+mid;
}
}
return NULL;
}
void testBinary()
{
int a[10]={0,1,3,5,45,78,98,111,121,454};
for (int i=9;i>=0;i--)
{
int *temp=BinarySearch(a,10,i);
if(temp==NULL)
{
cout<<"NULL"<<endl;
}
else
cout<<*temp<<endl;
}
}
//递归版本
int * BinarySearch_R(int *a,int n,int key,int left,int right)
{
if(a==NULL||n==0)
{
return NULL;
}
if(left<right)
{
int mid=left+(right-left)/2;
if(a[mid]>key)
{
return BinarySearch_R(a,n,key,left,mid);
}
else if(a[mid]<key)
{
return BinarySearch_R(a,n,key,mid+1,right);
}
else
{
return a+mid;
}
}
else
{
return NULL;
}
}
void testBinary_R()
{
int a[10]={0,1,3,5,45,78,98,111,121,454};
for (int i=9;i>=0;i--)
{
int *temp=BinarySearch_R(a,10,i,0,10);
if(temp==NULL)
{
cout<<"NULL"<<endl;
}
else
cout<<*temp<<endl;
}
}（2）左闭右闭 【】
int* BinarySearch_C(int *a,int n,int key)
{
if(a==NULL||n==0)
{
return NULL;
}
//[]
int left=0;
int right=n-1;
while(left<=right)
{
int mid=left+(right-left)/2;
if(a[mid]>key)
{
right=mid-1; //a[mid]的值已经判断过了
}
else if(a[mid]<key)
{
left=mid+1; //a[mid]已经判断过了
}
else
return a+mid；
}
return NULL;
}
void testBinary()
{
int a[10]={0,1,3,5,45,78,98,111,121,454};
for (int i=9;i>=0;i--)
{
int *temp=BinarySearch_C(a,10,i);
if(temp==NULL)
{
cout<<"NULL"<<endl;
}
else
cout<<*temp<<endl;
}
}
//递归版本
int * BinarySearch_CR(int *a,int n,int key,int left,int right)
{
if(a==NULL||n==0)
{
return NULL;
}
if(left<=right)
{
int mid=left+(right-left)/2;
if(a[mid]>key)
{
return BinarySearch_R(a,n,key,left,mid-1);
}
else if(a[mid]<key)
{
return BinarySearch_R(a,n,key,mid+1,right);
}
else
{
return a+mid;
}
}
else
{
return NULL;
}
}
void testBinary_R()
{
int a[10]={0,1,3,5,45,78,98,111,121,454};
for (int i=9;i>=0;i--)
{
int *temp=BinarySearch_CR(a,10,i,0,9);
if(temp==NULL)
{
cout<<"NULL"<<endl;
}
else
cout<<*temp<<endl;
}
}题目：
正整数数组a[0], a[1], a[2], ···, a[n-1]，n可以很大，大到1000000000以上，但是数组中每个数都不超过100。现在要你求所有数的和。假设这些数已经全部读入内存，因而不用考虑读取的时间。希望你用最快的方法得到答案。
提示：二分。
亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
