binary search algorithms using iterative and recursive

Question

I am looking for an element x in a sorted array. It compares xx or the array range equals to zero I am getting segmentation fault where I went wrong I couldn't find my code is below I am compiling in gcc complier.

#include <iostream>
using namespace std;

// iterative
int bsearch(int a[], int sz, int x)
{
  int low = 0;
  int high = sz -1;

  while(low <= high) {
    int mid = (low+high)/2;

    if(x < a[mid]) 
      high = mid - 1;
    else if(x > a[mid]) 
      low = mid + 1;
    else 
      return a[mid];
  }
  return -1;
}

// recursive
int bsearch_recursive(int a[], int low, int high, int x)
{
  if(low > high) return -1;

  int mid = (low + high)/2;

  if(x < a[mid])
    bsearch_recursive(a, low, mid-1, x);
  else if(x > a[mid])
    bsearch_recursive(a, mid+1, high, x);
  else
    return a[mid];
}

void print(int n)
{
  if(n == -1) {
    cout << "not found" << endl;
  return;
  }
  cout << "found" << endl;

}
int main()
{        
  int a[]={3, 7, 9, 16, 23, 34, 67, 87, 92};
  int arraySize = sizeof(a)/sizeof(int);
  int result;

  result = bsearch(a, arraySize, 7); 
  print(result);
  result = bsearch(a, arraySize, 92); 
  print(result);
  result = bsearch(a, arraySize, 77); 
  print(result);

  result = bsearch_recursive(a, 0, arraySize-1, 7); 
  print(result);
  result = bsearch_recursive(a, 0, arraySize-1, 92); 
  print(result);
  result = bsearch_recursive(a, 0, arraySize-1, 77); 
  print(result);

  return 0;
}

Answer 1

Below function has problem:

int bsearch_recursive(int a[], int low, int high, int x)

When you call this function recursively, you should return the value as shown below

int mid = (low + high)/2;
if(x < a[mid])
  return bsearch_recursive(a, low, mid-1, x);  // added return
else if(x > a[mid])
  return bsearch_recursive(a, mid+1, high, x);  // added return
else
  return a[mid];

If you don't return from some code paths of a function that returns, the code behavious is undefined.

As side notes

• if you intend to use this code for very large arrays, (low + high) may overflow, so use

int mid = low + (high - low)/2;

• To make sure your compiler warns you about this compile with -Wall option.
• Returning -1 in case of error is not a good idea if array may contain both positive and negative numbers. You can return array index if found and -1 if error or device some other not found mechanism.

Answer 2

Your recursive search needs to have a return value on each path, otherwise its results are undefined.

A recursive function works exactly like other functions - if it claims to be returning a value, it must do that. It doesn't just automatically return the result of the terminating recursive call.

int bsearch_recursive(int a[], int low, int high, int x)
{
    if(low > high) return -1;

    int mid = (low + high)/2;
    if(x < a[mid])
        return bsearch_recursive(a, low, mid-1, x);
    else if(x > a[mid])
        return bsearch_recursive(a, mid+1, high, x);
    else
        return a[mid];
}

Your compiler should have warned you about this - if it didn't, switch on more warnings.
If it did and you didn't care, start listening to warnings.