//***************************************************************** // R. A. Hillyard // binSearch.cpp // // Program to illustrate implementation of the binary search algorithm // on a sorted list. //***************************************************************** #include <iostream> using namespace std; int listSize = 15; int binSearch(char l[], int size, char key, int &count); int main() { int index; int count; char list[] = {'a','b','c','g','h','l','n','p','q','r','s','u','w','x','z'}; index = binSearch(list, listSize, 'a', count); if(index != -1) { cout << "found a at index: " << index <<" after "<<count<<" tries" << endl; } else cout << "did not find a" <<" after "<<count<<" tries"<< endl; index = binSearch(list, listSize, 'o', count); if(index != -1) { cout << "found o at index: " << index <<" after "<<count<<" tries" << endl; } else cout << "did not find o" <<" after "<<count<<" tries"<< endl; index = binSearch(list, listSize, 'p', count); if(index != -1) { cout << "found p at index: " << index <<" after "<<count<<" tries" << endl; } else cout << "did not find p" <<" after "<<count<<" tries"<< endl; } //***************************************************************** int binSearch(char l[], int size, char key, int &count) { int first = 0; //first element of the array int last = size-1; //last element of the array int mid; count = 0; while(last >= first) { count++; mid = (first+last)/2; //pick the middle of the list - round down if(l[mid] == key) //if key is in middle - return it return mid; else if(key < l[mid]) //search upper half of list last = mid-1; else first = mid+1; //search lower half of list }//end while return -1; }//end binSearch //***************************************************************** /******************Program output********************/ found a at index: 0 after 4 tries did not find o after 4 tries found p at index: 7 after 1 tries