SQL

Monday, 9 March 2015

Binary Search in Recursion C++

/*!
* file BinarySearchRecursion.cpp
* author Hasan
* date 25 June 2014 17:18:07
*/
#include <iostream>
#include <iomanip>
using namespace std;
const int SIZE = 15;
 
int binarySearch(const int[], intintint);
void printRow(const int[], intintint);
void printHeader(void);
int main()
{
 int a[SIZE], key, result;
 
 for (int i = 0; i < SIZE; ++i)
  a[i] = 2 * i;
 
 cout << "Enter a number between 0 and 28: ";
 cin >> key;
 
 printHeader();
 result = binarySearch(a, key, 0, SIZE - 1);
 
 if (result != -1)
  cout << '\n' << key << " found in array element " << result << endl;
 else
  cout << '\n' << key << " not found" << endl;
 
 cin.get();
 return 0;
}
 
int binarySearch(const int b[], int searchKeyint lowint high)
{
 int middle;
 
 if (low <= high) {
  middle = (low + high) / 2;
  printRow(blow, middle, high);
 
  if (searchKey == b[middle])
   return middle;
  else if (searchKey < b[middle])
   return binarySearch(bsearchKeylow, middle - 1);
  else
   return binarySearch(bsearchKey, middle + 1, high);
 
 }
 
 return -1; // searchKey not found
}// Print a header for the output
 
void printRow(const int b[], int lowint midint high)
{
 for (int i = 0; i < SIZE; ++i)
  if (i < low || i > high)
   cout<< "";
  else if (i == mid)
   cout << setw(3) << b[i] << '*'//mark middle value
  else
   cout << setw(3) << b[i] << " ";
 
  cout << '\n';
  
}
 
 
void printHeader(void)
{
 cout << "Subscripts:\n";
 
 for (int i = 0; i < SIZE; ++i)
  cout << setw(4) << i;
 
 cout << '\n';
 
 for (int k = 1; k <= 4 * SIZE; ++k)
  cout << '-';
 
 cout << '\n';
 cin.get();
}// print one row of output showing the current
// part of the array being processed.


output:

Enter a number between 0 and 28: 13
Subscripts:
   0   1   2   3   4   5   6   7   8   9  10  11  12  13  14
------------------------------------------------------------
  0   2   4   6   8  10  12  14* 16  18  20  22  24  26  28
  0   2   4   6*  8  10  12
  8  10* 12
 12*

13 not found


Enter a number between 0 and 28: 16
Subscripts:
   0   1   2   3   4   5   6   7   8   9  10  11  12  13  14
------------------------------------------------------------
  0   2   4   6   8  10  12  14* 16  18  20  22  24  26  28
 16  18  20  22* 24  26  28
 16  18* 20
 16*

16 found in array element 8

Post a Comment