CODEWITHSUNDEEP
c++recursion
The10thDoctor
The10thDoctor

Reputation: 125

Recursive Search with Array-Based Implementation

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
}

Upvotes: 1

Views: 463

Answers (1)

Dietmar K&#252;hl
Dietmar K&#252;hl

Reputation: 153840

A few notes:

  1. 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.
  2. 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.
  3. You need to deal with the situation that the sequence is empty.
  4. Personally, I wouldn't implement a binary search recursively, especially if the call isn't tail-recursive.
  5. When talking about personal preferences, I would implement it in terms of iterators anyway.

Upvotes: 2

Related Questions