CS115 lecture notes, Spring 1999
Week 12, Friday

Iterative version of bisection search
-------------------------------------

The "moving goal post" pattern

Start with low=0 and high=length-1

Calculate a mid point

Compare the target to the value at the mid point.

If equal, stop.

If less, then replace the upper goal post.

If more, replace then lower goal post.

Repeat while high >= low.


Analysis of bisection search
----------------------------

How many comparisons do you have to do in a linear search?

    One for each element of the array.
    If array size is n, there are n comparisons.

How many comparisons do you have to do in a bisection search?

    One each time we divide the array in half.

    How many times can we divide the array (size n) before
    we get to one?
    
    How many times do we have to double 1 before we get to n?

    What power of 2 is n?

    What mathematical function answers that question?


Mergesort
---------

Simple mergesort

1) split the deck in half

2) sort the halves

3) merge the halves

Is this faster than the traversal sorting we did before?
We'll analyze it next time and see.

Recursive mergesort

0) if the deck contains a single card, return it

1) split the deck in half

2) sort the halves (using mergesort)

3) merge the halves

Is this faster still?  We'll see.


The hardest part of implementing mergesort is merge.
Make sure you test merge rigorously before you write
the recursive version, or you will be unhappy.