Binary search looks for a specific value, which we refer to as a key in a sorted list of values. For example, it could be looking for a specific word in a dictionary, the word in this situation is the key, and the dictionary is the sorted list (it’s in alphabetical order).
Binary search takes in 4 parameters or input values, a lower bound position (which it will not search below), and an upper bound position (which it will not search above), a sorted list of values, and a key to search for.
If it finds the key it outputs the position of the key in the list.
If it does not find the key, it indicates that it didn’t find it.
Learn the basics of big-O notation
Determine why binary search uses O(log2n) or logarithmic time in its worst case
Determine why binary search uses O(1) or constant extra memory in any case, i.e. it works in-place.
Go through some implementation pitfalls and how to avoid them.
Song and Code
Hear the 17-line, 1 minute 45 second binary search song:
The first part covers big-O analysis facts.
The second covers the pseudocode which will help you program binary search in any programming language.
Watch me demonstrate how to use the song lyrics to implement the algorithm in Python, the most straightforward programming language (in my opinion).