/*! * 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[], int, int, int); void printRow(const int[], int, int, int); 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 searchKey, int low, int high) { int middle; if (low <= high) { middle = (low + high) / 2; printRow(b, low, middle, high); if (searchKey == b[middle]) return middle; else if (searchKey < b[middle]) return binarySearch(b, searchKey, low, middle - 1); else return binarySearch(b, searchKey, middle + 1, high); } return -1; // searchKey not found }// Print a header for the output void printRow(const int b[], int low, int mid, int 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