首页 > 代码库 > 二分查找需要注意的Bug
二分查找需要注意的Bug
不应该使用Middle=(left+right)/2这种情况，否则对于大数据来说会产生溢出问题。切记！值不同的时候，left相对Middle应该+1，不要直接用Middle进行赋值。
#include <iostream>
#include <set>using namespace std;
//下面一个移位是一样的，>>相当于除去2，主要是要用right-left，否则对于大数据来说会产生溢出问题。切记
int binarySearch(int arr[],int len,int number)
{
int left=0;
int right=len-1;
int middle;
while (left<=right)
{
middle=left+(right-left)/2;
if (arr[middle]<number)
{
left=middle+1;
}
else if (arr[middle]>number)
{
right=middle-1;
}
else
{
return middle;
}
}
}
int main()
{
//multiset<int> si;
//si.insert(1);
//si.insert(2);
//si.insert(6);
//si.insert(2);
//si.insert(4);
//si.insert(5);
//multiset<int>::iterator i;
////set<int>::const_iterator ibegin,iend;
////iend=si.end();
//for (i=si.begin();i!=si.end();i++)
//{
// cout<<*i<<endl;
//}
int array1[]={0,10,20,30,40};
int ret;
ret=binarySearch(array1,5,40);
cout<<ret<<endl;
return 0;
}
//int binary_search(int array[],int n,int value)
//{
// int left=0;
// int right=n-1;
// //如果这里是int right = n 的话，那么下面有两处地方需要修改，以保证一一对应：
// //1、下面循环的条件则是while(left < right)
// //2、循环内当array[middle]>value 的时候，right = mid
//
// while (left<=right) //循环条件，适时而变
// {
// int middle=left + ((right-left)>>1); //防止溢出，移位也更高效。同时，每次循环都需要更新。
//
// if (array[middle]>value)
// {
// right =middle-1; //right赋值，适时而变
// }
// else if(array[middle]<value)
// {
// left=middle+1;
// }
// else
// return middle;
// //可能会有读者认为刚开始时就要判断相等，但毕竟数组中不相等的情况更多
// //如果每次循环都判断一下是否相等，将耗费时间
// }
// return -1;
//}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。