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 ...

Get Everyday Data Structures now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.