Notes for Lecture - March 21, 2003

Binary Search

Imagine you have file cabinet.  It holds one million pieces of paper, and you need to find one.  One simple stategy you can employ is looking through it one piece at a time until you find it.  That will work, though it could take one million tries.  Let's imagine that you ordered the papers, put them in some kind of alphabetical order (ordered by subject let's say).  Now you can just look for a paper, but going for a paper somewhere in the middle and then see if that's above or below the subject you're looking for alphabetically and thus exclude 1/2 of the total papers in one try.  Well, if there are a million papers in there, you just got rid of 500,000 that you don't need to bother with.  You can do this again by looking at the middle of the remaining half and judging which half of the remaining half your paper belongs in.  You just made your stack 1/2 as big again.  Guess what?  You're now running a binary search algorithm!  The basic idea of binary search is that if you have a sorted vector of data, you can search through it by the divide and conquer idea.  Meaning you can take a look at the middle, and then based on what the value of that is you can figure out if what you're looking for belongs in the top and bottom half.  Once you know the correct half, you can run the algorithm on the remaining half.  (sounds recursive, doesn't it?)

Quick Sort

The knowledge you need of this is considerably less.  You should know what it is, and that it is a good deal faster at sorting large vectors than binary search, and roughly how it works.  I commented up some example code, and that should mostly suffice for information on this sort.