Lecture 33

Announcements

Talking Points

Given a list of numbers, how can you find if 8 is in the list?

Given two ways to find if it is there, how can you decide which one is better?

We'll discuss linear, bogo, and binary search in class.

If we have time, we'll also discuss how searching can be used to sort a list.

From Lecture

Linear Search

Look at each element in order.

Works for all lists.

For a list with n elements, takes no more than n steps to find the value or report it is not present.

Bogo Search

Look at a random element, repeat.

Works for all lists but only if the element is present.

For a list with n elements, on average takes about n steps to find the value; runs forever if it is not present.

Binary Search

Look in the middle and, if we didn't find it, consider only the half where it could be and repeat. This is how people look up things in alphabetized lists.

Works for lists if their values are in order, but not otherwise.

For a list with n elements, takes no more than about log₂(n) steps to find the value or report that it is not present.

Selection Sort

Find the smallest value in the unsorted part of the list and more it to the end of the sorted part of the list. Repeat until the whole list is sorted.

Works for all lists.

For a list with n elements, takes no about n² steps: n searches for minumum value, each of which takes about n steps (note: there are faster sorting algorithms out there).