Random Search
~~~~~~~~~~~~~

-Keep trying random elements until found

Pro:
* Can be used on a unsorted list
* Easy to use

Con:
* Requires source of randomization
* No way to keep track of checked elements
(Unless no replacement, but then one time only or must replace
itemns after search.)
* Requires random access
* Slow

Linear Search
~~~~~~~~~~~~~

-try items in order

Pro:
* can be used on unsorted list
* easy to use
* does not require random access

Con:
* slow for large lists

Binary Search
~~~~~~~~~~~~~

- check middle, compare, discard half, etc.

Pro:
* very fast (requires log n comparisons)

Cons:
* Requires a sorted list
* requires random access


Interpolation Search
~~~~~~~~~~~~~~~~~~~~~

- approximates how far the item is from the current position
(phone book)

Pro:
* extremely fast (often better than binary, because doesn't divide search
space in half)

Cons:
* same as binary search
* assumes a uniform distribution of data


Binary vs. Interpolation:

Interpolation is often faster in terms of number of comparisons, but in
practice it's more difficult to implement (requres some calculation to
interpolate positions), so binary is most often used.

----------------------------------------------

What to do when the item is not the list?
* Say so
* Perhaps return nearest (in some sense) item 

How to return nearest?
* Sorted list: get 2 adjacent elements, compare, return nearest
* Unsorted: keep track of how close we get during the trials

----------------------------------------------

Sorted vs. Unsorted Lists

Sorted:
* Fast search
* Easy to find nearest
* east to get statistics (max/min, median, ranges)

Unsortes:
* Requires no maintenance (insert anywhere)