Recursive Search with Array-Based Implementation

Question

I'am having some trouble with this program and I can not figure what I'am doing wrong; the program is supposed to be a recursive search program, however some of the functions are not being called correctly (or at all). The problem seems to center around the "bin_search" portion, and again an error pops up on the "int data [size]" portion, saying "Variable-sized object may not be initialized". Any help would be greatly appreciated. Thanks in advance!

# include <iostream> // Allows program to perform input and output
using std::cout; // program uses cout
using std::cin; // program uses cin



int bin_search ( int data[], int left, int right, int key, int NOT_FOUND)
{
 // calculate the index to search
 int index = ( ( ( key - data[ left ]) / ( data[ right ] - data[ left] ) )* (right - left)         ) + left;
 // terminating condition
 if ( data[index] == key )
 return key;
 // terminating condition
 if ( left >= right )
 return NOT_FOUND;
 // search recursively
 if ( key < data[index] )
 return bin_search ( data, left, index-1, key );
 else
 return bin_search ( data, index + 1, right, key );
}
    // end function bin search

int main()
{
 // function main begins program execution
  int size = 10;
  int bin;
  int data[size] = {0, 7, 12, 23, 44, 335, 426, 477, 658, 921};
  int key = 23;
 // let the user know about the program
 cout << "\n\n A program to search an element recursively.";
 // search and print the results to the user
 if ( bin_search( data, 0, size-1, key ) == key )
 cout << "\n\n\tThe key was found.";
 else
 cout << "\n\n\tThe key was not found.";
 // let the screen wait to see the output
 cout << "\n\n\t";
 system( "pause" );
 return 0; // indicate program executed successfully
 // end of function, main
}

Dietmar Kühl · Accepted Answer · 2013-08-25 02:19:29Z

2

A few notes:

When there are n elements, you want to have n + 1 positions! This way you can easily deal with an empty sequence and there is an obvious result to return if something isn't found.
Your computation to locate the index to check is far to complicated. All you want is to find the middle position of the sequence to search. The key is certainly not part of this computation.
You need to deal with the situation that the sequence is empty.
Personally, I wouldn't implement a binary search recursively, especially if the call isn't tail-recursive.
When talking about personal preferences, I would implement it in terms of iterators anyway.

answered Aug 25, 2013 at 2:19

Dietmar Kühl

155k18 gold badges238 silver badges395 bronze badges

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

1 Comment

Konrad Rudolph Over a year ago

+ the elephant in the room, the array declaration is invalid.

Collectives™ on Stack Overflow

Recursive Search with Array-Based Implementation

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related