O'Reilly logo

Everyday Data Structures by William Smith

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required