Background

The binary search algorithm is used to find a value within an ordered list. The list must be ordered for this algorithm. The time complexity of this algorithm is O(log(n)) where n is the number of items in the list.

Altorithm Steps

1. Find the midpoint of the array.
2. If midpointVal == searchVal, return true
3. If not, check if midpointVal is less than or greater than searchVal
4. If midpointVal > searchVal, repeat steps 2 and 3 for the left sublist
5. If midpointVal < searchVal, repeat steps 2 and 3 for the right sublist
6. Repeat this process until searchVal is found, or until there's 1 element
7. If the last element doesn't match searchVal, return false

More information

See the image below for an example of the data structure that could be used for a binary search. The image depicts a list of length 7 that is sorted.