Binary Search

Binary search looks for a specific value, which we refer to as a key in a sorted list. 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(log₂n) 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.
• Discuss applications.

• Hear the 17-line, 1 minute 45 second binary search song:
  1. The first part covers big-O analysis facts.
  2. 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).