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 search would begin...