3. Binary Search

This is a good search algorithm to use IF the list is sorted in some kind of order

For example, the following list is in increasing order:

                                3,6,9,15,27,34,56,73

Algorithm:

1. Let the item to be searched for be T
2. Examine the midmost item in the list to see if it is T
3. If it was, then it has been found and return its position
4. If it is higher than the middle,
   1. then examine the next one up.
   2. Adjust the bottom of the list to be this one
   3. If it not T then examine the next element and adjust the bottom of the list so the list is becoming shorter each time
   4. Repeat until found or the end of list is reached and return as not found
5. If it is lower than the middle
   1. Examine the next one down and adjust the top of the list to be this item
   2. If it is not this one, then examine the next lower one and again adjust the top each time
   3. Repeat until it is found or the beginning of the list is reached and it is not found

The good thing about binary search is that the worst case and average case are the same and so there is a guaranteed maximum number of steps to find an item in the list of length n. And with a space complexity of O(1) it means it can be coded with a fixed amount of storage or memory.