ABSTRACT
A binary search is an efficient way to search for something in a sorted array. The function definition should be something like:
int search( int * arr , int len , int key)1
The function search returns the index of key within arr. If arr does not contain this key, then the function returns −1. The arguments mean the following: • arr: an array of integers. The elements are distinct and sorted in the ascending order. • len: the length of the array, i.e., the number of elements in the array. • key: the value to search for. Think of key as the proverbial needle in the haystack. Since the array is already sorted, it is possible to quickly discard many elements by
comparing key with the element at the center of the array. If key is larger than that element, we do not need to search the lower part of the array, i.e., the part before the center element. If key is smaller than that element, we do not need to search the upper part of the array. This idea can be generalized such that instead of considering the whole array, we are only considering a contiguous part of the array. As such, there are four scenarios: • If the contiguous part of the array has no elements, then it is impossible to find key
and the function returns −1. • If key is the same as the center of the contiguous part of the array, then the index
has been found, and we return that index. • If the key is greater than the center element, then the function discards the lower half
(the elements with smaller values) of the array, and considers the upper half.
