Start a new topic
Add Reply
#include <iostream>
#include <iomanip>
using namespace std;
// binary search prototype
int binarySearch( int a[], int first, int last, int key, int count );
int main()
{
const int size = 18;
int arr[size] = { 1, 2, 5, 7, 9, 12, 13, 17, 19, 20, 25, 48, 56, 78, 81, 89, 93, 96};
int searchkey = 0;
// Displays the sorted array list
for ( int i = 0; i < size; i++ )
{
cout << setw(4) << arr[i];
if ( (i + 1) % 5 == 0 ) cout << endl;
}
// prompts the user to enter a value
while ( searchkey != -1 )
{
cout << "\nEnter a search key (-1 to quit): ";
cin >> searchkey;
if ( searchkey == -1 ) break;
// displays results
int repetitions = binarySearch( arr, arr[0], size, searchkey, 0 );
cout << "The key has been found after "<<repetitions<<" repetitions\n";
}
return 0;
}
// RECURSIVE BINARY SEARCH FUNCTION
int binarySearch( int a[], int first, int last, int key, int count )
{
int middle = (first + last) / 2;
if ( key == a[middle] )
{
return count;
}
else if ( key < a[middle] )
{
count +=1;
return binarySearch( a, first, middle-1, key, count );
}
else if ( key > a[middle] )
{
return binarySearch( a, middle+1, last, key, count );
count +=1;
}
return -1;
}
*** MOD EDIT: Added code tags. Please
***
This post has been edited by JackOfAllTrades: 24 April 2009 - 05:00 PM
MultiQuote
| 
