CS151 lecture notes, Fall 1999
Week 11, Wednesday

hw10 solutions are now online.

Workers and wrappers
--------------------

totalWorker is called a worker because it actually performs
the computation (unlike the wrapper we are about to see).

It is also a very general form of the method, since it can
find the sum of any range of the array.

Most of the time, though, we don't want the most general
form; we just want to add up _all_ the elements of the array.

Of course, we can do that easily:

    int total = totalWorker (a, 0, a.length-1);

But it is clumsy.  Instead, we write a simple method called
total, that takes a single parameter, and that invokes totalWorker

  public static int total (int[] a) {
    return totalWorker (a, 0, a.length-1);
  }

It's called a wrapper because it encapsulates the single line
of code.

Also sometimes called a veneer, because it is a thin covering
that improves the appearance of a coarse underlayer.


Arrays of objects
-----------------

Keys ideas:

1) when you create an array of Object types, you get an
   array of null references

2) you have to use new (repeatedly) to actually create the
   objects.

   Card[] deck = new Card[52];

   deck[0] = new Card (0, 1);
   deck[1] = new Card (0, 2);

   The book 12.6 contains a loop that allocates
   52 different cards.

3) You can compose the syntax for accessing arrays and
   accessing instance variables.

   card[i].rank          the rank of the ith card

   suits[card[i].suit]   the name of the suit of the ith card

   Composition is cool, but of course you want to show restraint.


Cards and aliasing
------------------

Arrays can share objects.

The arrays contain references to the same objects -- aliasing.

For things like Cards, which are immutable, aliasing is less
dangerous.

Homework 11 involves this kind of aliasing.



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?