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

I am unable to figure out which line is forcing the code to segmentation fault. — user3632872
– user3632872, Commented Jun 3, 2014 at 9:36
Use a debugger. You can google for gdb tutorial to learn how to debug. And then find the failing line. — Mohit Jain
– Mohit Jain, Commented Jun 3, 2014 at 9:38

πάντα ῥεῖ · Accepted Answer · 2014-06-03 21:33:29Z

4

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.

edited Jun 3, 2014 at 21:33

πάντα ῥεῖ

88.9k13 gold badges125 silver badges199 bronze badges

answered Jun 3, 2014 at 9:52

molbdnilo

67.1k3 gold badges46 silver badges90 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Matthieu M. Over a year ago

You might want to include typical compiler flags to activate warnings (-Wall for gcc/clang, /W for MSVC I believe).

πάντα ῥεῖ · Accepted Answer · 2014-06-03 21:34:10Z

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.

Collectives™ on Stack Overflow

binary search algorithms using iterative and recursive

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related