// From the software distribution accompanying the textbook // "A Practical Introduction to Data Structures and Algorithm Analysis, // Third Edition (C++)" by Clifford A. Shaffer. // Source code Copyright (C) 2007-2011 by Clifford A. Shaffer. // Perform binary search on an array. There are two versions: // One that uses a template and a comparator, and one that works // only for a simple int array. #include "book.h" #include "compare.h" // This version is generalized to use a template for elements, // and a comparator. // Return the position of an element in a sorted array of // size n with key value K. If none exist, return n. template int binaryt(E array[], int n, Key K) { int l = -1; int r = n; // l and r are beyond the bounds of array while (l+1 != r) { // Stop when l and r meet int i = (l+r)/2; // Check middle of remaining subarray if (Comp::lt(K, getKey::key(array[i]))) r = i; // In left half if (Comp::eq(K, getKey::key(array[i]))) return i; // Found it if (Comp::gt(K, getKey::key(array[i]))) l = i; // In right half } return n; // Search value not in array } // This is the version that appears in the book. // It works on an integer array. // Return the position of an element in sorted array "A" of // size "n" with value "K". If "K" is not in "A", return // the value "n". int binary(int A[], int n, int K) { int l = -1; int r = n; // l and r are beyond array bounds while (l+1 != r) { // Stop when l and r meet int i = (l+r)/2; // Check middle of remaining subarray if (K < A[i]) r = i; // In left half if (K == A[i]) return i; // Found it if (K > A[i]) l = i; // In right half } return n; // Search value not in A } // Test program to test out both the specific and the generic bsearch // algorithm. int main(int argc, char** argv) { int i, numvals, K, result; int* A; Int* B; Int** C; Assert(argc == 3, "Usage: bsearch "); numvals = atoi(argv[1]); K = atoi(argv[2]); // Create and initialize array A = new int[numvals]; B = new Int[numvals]; C = new Int*[numvals]; for (i=0; i(A, numvals, K); if (result == numvals) cout << "Binary search was unsuccessful\n"; else cout << "Binary search returns " << result << "\n"; result = binaryt(B, numvals, K); if (result == numvals) cout << "Binary search was unsuccessful\n"; else cout << "Binary search returns " << result << "\n"; // Call to generalized template form result = binaryt(C, numvals, K); if (result == numvals) cout << "Binary search was unsuccessful\n"; else cout << "Binary search returns " << result << "\n"; return 0; }