Binary Search

Searching, or looking for something in a collection, is one of the most common tasks we perform on a daily basis. Whether it's searching for a name in the phone book, or glancing around for an item in a grocery aisle-- we generally will need to find stuff, and we'd like to do it fast.

The way we search for an item typically depends on how the items are arranged. For example, if books in a library weren't kept in a systematic way, then one would have to examine every book randomly until the desired book is found. However, thanks to categories, alphabetical ordering methods, and the Dewey Decimal Classification; books are pretty easy to find nowadays. Similarly, in the case of the phone-book, one can directly jump to the initials of a name.

The binary search technique, as the name suggests, is used to search for an element in a list of elements. Though linear search is a simple alternative to binary search, the time complexity of linear search is O(n). This is bad, because it means that if element exists at the last index, the whole list has to be iterated. Binary search reduces the search complexity to O(log(n)).

Let's explore this more.