Follow

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use
Contact

Binary Search enters a infinite loop when I use a 'for' Loop but works fine 'while' while loop

I am learning Binary Search and these are my attempts.

So here are two pieces of code, both of them being same with the only difference being one is in while loop while the other is in for loop.

int binarySearch(int *input, int n , int val) {
  int high = n-1, low =0;
  while (low <= high) {
    int mid = (high+low) / 2;

    if (input[mid] == val)
      return mid;

    if (input[mid] < val)
      low = mid + 1;

    else
      high = mid - 1;
  }

  return -1;
}
int binarySearch(int *input, int n, int val)
{
    int start=0, end=n-1, mid ;
    for (int i = start ; i<= end;) {
        mid = (end+start)/2 ;
        if ( input[mid] == val) {
            return mid;
        }
        else if (input[mid] > val) {
            end = mid-1;
        }
        else {
            start = mid+1;
        }
    }
    return -1;
}

Here is the main() Function :

MEDevel.com: Open-source for Healthcare and Education

Collecting and validating open-source software for healthcare, education, enterprise, development, medical imaging, medical records, and digital pathology.

Visit Medevel

#include <iostream>
using namespace std;

int binarysearch(int *input,int n,int val);

int main()
{

    int size;
    cin >> size;
    int *input = new int[size];

    for(int i = 0; i < size; ++i)
    {
        cin >> input[i];
    }
    
    int t;
    cin >> t;

    while (t--)
    {
        int val;
        cin >> val;
        cout << binarySearch(input, size, val) << endl;
    }
    
    delete [] input;
    return 0;
}

The input format for test cases is given as

The first line contains an Integer 'N' which denotes the size of the array/list.

Second line contains 'N' single space separated integers representing the elements in the array/list.

Third line contains an Integer 't' which denotes the number of test cases or queries to be run. Then the test cases follow..

All the 't' lines henceforth, will take the value of X to be searched for in the array/list.

The test cases is :

11
1 4 8 10 15 19 24 28 32 33 35
1
40

Now what I get when i use for loop is an infinte loop but when i use a while loop the test case passes.

Why is this happening ? Aren’t for loop and while loop interchanable ?

>Solution :

The difference is that in the while loop you are comparing low and high

while (low <= high) {

while in the for loop you are comparing i and end

or (int i = start ; i<= end;) {

and within the for loop values of i and end can be unchanged due to this else statement

    else {
        start = mid+1;
    }

that results in undefined behavior.

You need to change the variable i instead of the variable start

   mid = (end+i)/2 ;

   //...

    else {
        i = mid+1;
    }
Add a comment

Leave a Reply

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use

Discover more from Dev solutions

Subscribe now to keep reading and get access to the full archive.

Continue reading