Binary Search

Binary Search | Bubble Sort | Selection Sort | Finding Maximum Value | Linear Search | Celsius to Fahrenheit | 10 Pseudo-random numbers | Calculating Average | Swapping Values | Lowercase/ Uppercase

Binary Search - A 'divide and conquer' technique to search the list

Advantage:      Faster than a sequential search

Requirement:  The list must be sorted

C++ Program

 ```#include int BinarySearch(int [], int, int); int main() {``` ``` const int NUMEL = 10; int nums[NUMEL] = {5,10,22,32,45,67,73,98,99,101}; int item, location; cout << "Enter the item you are searching for: "; cin >> item; location = BinarySearch(nums, NUMEL, item); if (location > -1) cout << "The item was found at index location " << location << endl; else cout << "The item was not found in the list\n"; return 0; } // this function returns the location of key in the list // a -1 is returned if the value is not found ``` ```int BinarySearch(int list[], int size, int key) ``` ```{ int left, right, midpt; left = 0; right = size - 1; while (left <= right) { midpt = (int) ((left + right) / 2); if (key == list[midpt]) { return midpt; }``` ``` else if (key > list[midpt]) left = midpt + 1; else right = midpt - 1; } return -1; }```