# Binary Search

##### Intuition

Learn how to perform binary search yourself (without a computer) to develop a feel for the algorithm.

#### Intuition:

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.

Since the input list is sorted binary search can look for the key in an efficient manner. It looks at the middle element between the low and high indices.

- If the key is less than the value here it resets the high to one less than this position
- If the key is greater than the value here it resets the low to one less than this position
- If neither of these two conditions have been met the key exists at the middle index.
- It keeps performing these steps until the key has been found or the low index has exceeded the high index

##### Analysis

Analyze the runtime and memory usage with big-O notation, and discuss potential programming bugs of binary search.

#### Analysis:

- Learn the basics of big-O notation
- Determine why binary search uses
*O(log*or logarithmic time in the worst case_{2}n) - Determine why binary search uses
*O(1)*or constant extra memory in any case, i.e. it works in-place. - Discuss potential programming bugs and get a mini-lesson on binary number representation.
- Briefly discuss applications.

##### Song and Code

MEMORIZE binary search by learning the musicAlgo and see me use the lyrics to code the algorithm.

#### Song and Code:

- Hear the 17-line, 1 minute 45 second binary search song:
- The first part covers big-O analysis facts and a general description of the algorithm.
- 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).

#### Intuition:

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.

#### Analysis:

- Learn the basics of big-O notation
- Determine why binary search uses
*O(log*or logarithmic time in its worst case_{2}n) - 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.

#### 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 selection sort 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).