Chapter 2: Arrays

The Array Workshop Applet. 
   Insert is fast ... append to the end
   Delete is slow ... begins with a search for the item to be deleted
      how can the workshop applet be speeded up?
   Search is slow ... whether sucessful or unsuccessful
      worst-case scenario requires peeking at every entry
      average successful search requires peeking at about half of the entries
      average unsuccessful search requires peeking at every entry

The Basics of Arrays in Java. 
   Arrays are objects.  Usually created by using the 'new' keyword.
   Each has a length attribute.  
   
Dividing a Program into Classes. 
   Chunks of code that access or manipulate data can be packaged with the data.
   Sometimes, these things turn out to be reusable.
   
Class Interfaces. 
   Describe the public methods (and public fields, if any) in the class.
   
The Ordered Array Workshop Applet.
   Two implementation options: linear search or binary search, no duplicates allowed
   Inserting and deleting require searching as a subtask
      You have to find the item to be deleted (a search)
      You have to find the location where a new item will be inserted (a search)
   
   Linear insert is slow ... binary search speeds it up slightly
   Linear delete is slow ... binary delete is faster
   Linear search is slow ... binary search is faster
      linear search: worst-case scenario requires peeking at every entry
                     average search requires peeking at about half of the entries
      linear or binary: insert/delete require moving, on average, half of the entries

Java Code for an Ordered Array.
   The essential operations are insert, delete, search (binary search, of course)

Logarithms. (lg = base 2 logarithm, log = base 10 logarithm, ln = natural logarithm)
   2**10 = 1024, so 10 = lg(1024);  if 2**K=N then K=lg(N)
   10**3 = 1000 so 3 = log(1000);  if 10**x=y then x = log(y)
   Allows you to solve for exponents in some simple equations and formulas.

Storing Objects. 
   You can create an array whose elements are objects.

Big O Notation
   Let f be a real-valued function whose domain is the natural numbers N.  I.e., f:N->R
   O(f(n)) = { g:N->R | for some positive constant c and some index K, n>K => g(n)<c.f(n)}
   
   Note that O(f) is a set of functions
   
   The function g(n) is in O(f(n)) if and only if
      g(n) is bounded above by a multiple of f(n) when n is large.

Why Not Use Arrays for Everything. 
   Other structures are more efficient from time to time.