the code when executes creates an infinite loop.

What is wrong with this code :-(

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;
}

CodePudding user response：

I see you wrote your code only for specific count of numbers. For reference, here is my preferred way of doing binary search:

#include <iostream>
#include <cassert>
#include <vector>
#include <algorithm>
using namespace std;

/**
 * @brief
 *
 * @param arr
 * @param x         - item which is needed to be find
 * @param left      - start point
 * @param right     - end point
 * @return long
 */
long find_binary(vector<long> &arr, long x, long left, long right)
{
    if (right >= left)
    {
        long half = left   (right - left) / 2;

        if (x == arr[half])
        {
            return half;
        }
        if (x > arr[half])
        {
            return find_binary(arr, x, half   1, right);
        }
        return find_binary(arr, x, left, half - 1);
    }

    return -1;
}

/**
 * @brief
 *
 * @param n     - count of arr
 * @param m     - count of searching elements
 * @param arr   - elements of an array
 * @param b     - elements which needed to be find
 *
 * @return int
 */
int main()
{
    int n;
    cin >> n;
    vector<long> arr(n);
    for (size_t i = 0; i < arr.size(); i  )
    {
        cin >> arr[i];
    }

    // sorting all elements in asc order
    sort(arr.begin(), arr.end());

    int m;
    cin >> m;
    vector<long> b(m);
    for (int i = 0; i < m;   i)
    {
        cin >> b[i];
    }

    for (int i = 0; i < m;   i)
    {
        cout << find_binary(arr, b[i], 0, (long)arr.size()) << " ";
    }

    return 0;
}

CodePudding user response：

Answering your actual question: "What is wrong with this code?", see comments below:

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 (array[mid] < item)
            start = mid   1;
        else
            end = mid - 1;
     }
     cout << "Not found." << endl;
     return 0;
}

CodePudding user response：

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;
}

See the changes between ** in the if checks inside the loop. It works now.

EDIT: Added a termination condition if the element is NOT found in the array. Your original code was looping infinitely because your conditions were wrong. The corrections in ** fixed the condition when the searched for element was actually inside the array. And now the termination condition takes care of the last case of infinite loop as well.