首页 > 代码库 > 二分查找需要注意的Bug

二分查找需要注意的Bug

2024-07-04 10:44:49   225人阅读

不应该使用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;  
//} 


联系
我们