C plus 中的二分查找

Question

执行时的代码创建了一个无限循环。

这段代码有什么问题:-(

using namespace std;

int main(){
 int arr[10]={1,20,30,75,90,189,253,302,304,455}, start=0, end=9, item, mid, i;
 cin>>item;
 mid=(start+end)/2;
 while(arr[mid]!=item){
     mid=(start+end)/2;
     if(item>mid){
         start=mid+1;
     }
     else if(item<mid){
         end=mid-1;
     }
 }
 cout<<"Found at location : "<<mid<<endl;
 return 0;
}

Answer 1

using namespace std;
int main(){
   int arr[10]={1,20,30,75,90,189,253,302,304,455}, start=0, end=9, 
   item, mid, i;
   cin>>item;
   bool found = true;
   mid=(start+end)/2;
   while(arr[mid]!=item ){
       mid=(start+end)/2;
       if(item > **arr[mid]**){
          start=mid+1;
       }
       else if(item< **arr[mid]**){
          end=mid-1;
       }

       if ( start > end ){ // termination condition
          found = false; break;
       } 
   }
 
   if ( found ) std::cout<<"Item found at: "<<mid<<std::endl;
   else std::cout<<"Item not found."<<std::endl;
}

查看循环内 if 检查中 ** 之间的变化。现在可以使用了。

编辑：如果在数组中找不到该元素，则添加终止条件。您的原始代码无限循环，因为您的条件错误。 ** 中的更正修复了搜索元素实际上在数组内部时的情况。现在终止条件也处理了无限循环的最后一种情况。

Answer 2

回答您的实际问题：“此代码有什么问题？”，请参阅以下评论：

using namespace std;

int main(){
    int arr[10] = {1,20,30,75,90,189,253,302,304,455}, start=0, end=9, item, mid, i;
    cin >> item;
    mid = (start+end) / 2;
 
    // You function loops indefinitely...  The first place to look is here, at 
    // the test for your loop.
    // One thing is quite plain here :  You will loop indefinitely if the item you 
    // search for is not in the list.
    //
    // You should also stop looping when your search interval has reduced to 
    // nothingness, as this indicates the item is not found...
    //
    while (arr[mid] != item) {  // <-- BUG

    // try this instead: 
    while (start <= end) {  // loop while interval size is >= 1 ('end' is inclusive)
        const int mid = (start + end) / 2;

        // Check for search success here:
        if (arr[mid] == item)            
        {
            cout << "Found at location : " << mid << endl;

            return 1;    // we're done! exit loop
        }

        if (item > mid) { // <-- BUG!!!

        // should be

        if (arr[mid] < item)
            start = mid + 1;
        else
            end = mid - 1;
     }
     cout << "Not found." << endl;
     return 0;
}

C plus 中的二分查找

Binary Search in C plus plus

c++

binary-search