Binary search in array is not working properly [closed]

// function for binary search in array
#include <iostream>
using namespace std;
int binSrch(int arr[], int n, int key)
{
    int s = 0, e = n; // s for starting and e for ending
    int mid = (s + e) / 2;
    while (s <= e)
    {
        if (arr[mid] == key)
            return mid;
        else if (arr[mid] > key)
            e = mid - 1;
        else
            s = mid + 1;
    }
    return -1;
}
int main()
{
    int n, key;
    cout << "enter no. of elements" << endl;
    cin >> n;
    int arr[n];
    cout << "enter array " << endl;
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }
    cout << "enter key" << endl;
    cin >> key;
    cout << binSrch(arr, n, key);
    return 0;
}

This code for binary searching in array does not work.

For some array the program gets stuck. I don’t know what did wrong.

I entered input in sorted format.

PS C:UsersanmolDesktopc++projectwork> g++ .binSearchArrFun.cpp
PS C:UsersanmolDesktopc++projectwork> ./a
enter no. of elements
6
enter array 
2
3
4
5
6
7
enter key
8

it just stuck here rather than giving -1

Answer

I modified your code. Run it and it should become clear what’s going on.

#include <iostream>

using namespace std;

int binSrch(int arr[], int n, int key)
{
  int s = 0, e = n; // s for starting and e for ending
  int mid = (s + e) / 2;
  while (s <= e)
  {
    if (arr[mid] == key)
      return mid;
    else if (arr[mid] > key)
    {
      cout << "e = mid - 1;n";
      e = mid - 1;
    }
    else
    {
      cout << "e = mid - 1;n";
      s = mid + 1;
    }
  }
  return -1;
}

int main()
{
  int n = 4, key = 3;
  int arr[100] = { 1,3,4,10 };

  cout << binSrch(arr, n, key);
  return 0;
}

You can use this modified main for testing. It ouputs test cases that don’t work.

int main()
{
  int n = 4;
  int arr[] = {1,3,4,10,11};

  // check for each element of arr if it is found
  // at the right position

  int index = 0;
  for (auto testval : arr)
  {
    if (! binSrch(arr, n, testval) == index)
      cout << "not OK for case" << testval << "n";

    index++;
  }

  // check if 0 and 100 are not found

  if (binSrch(arr, n, 0) != -1)
    cout << "not OK for case" << 0 << "n";

  if (binSrch(arr, n, 100) != -1)
    cout << "not OK for case" << 100 << "n";  

  return 0;
}