Binary search

When dealing with an unsorted collection, a sequential search is probably the most reasonable approach. However, when working with a sorted collection there are better methods of finding matches to search keys. One alternative is a binary search. A binary search is typically implemented as a recursive function and works on the principle of repeatedly dividing the collection in half and searching smaller and smaller chunks of the collection until a match is found or until the search has exhausted the remaining options and turns up empty.

For example, given the following set of ordered values:

S = {8, 19, 23, 50, 75, 103, 121, 143, 201}

Using a linear search to find the value 143 would have a complexity cost of O(8) since 143 is found at index 7 (position 8) in our collection. However, a binary search can take advantage of the sorted nature of the collection to improve upon this complexity cost.

We know that the collection consists of nine elements, so the binary...