Rice University - Comp 212 - Intermediate Programming

Spring 2006

Lecture #27 - Array-Based Dictionary; Binary Search and Interpolation Search

Arrays in Java

Arrays...

are objects,
are dynamically created (via new), and
may be assigned to variables of type Object.

An array object contains zero or more unnamed variables of the same type. These variables are commonly called the elements of the array.
A non-negative integer is used to name each element. For example, arrayOfInts[i] refers to the i+1st element in the arrayOfInts array.

Array Types

An array type is written as the name of an element type followed by one or more empty pairs of square brackets.

For example, int[] is the type corresponding to a one-dimensional array of integers.

An array's length is not part of its type.
The element type of an array may be any type, whether primitive or reference, including interface types and abstract class types.

Array Variables

Array variables are declared like other variables: a declaration consists of the array's type followed by the array's name. For example,

double[][] matrixOfDoubles;

Declaring a variable of array type does not create an array object. It only creates the variable, which can contain a reference to an array.
Because an array's length is not part of its type, a single variable of array type may contain references to arrays of different lengths.
To complicate declarations, C/C++-like syntax is also supported, for example,

double rowvector[], colvector[], matrix[][];

double[] rowvector, colvector, matrix[];

double[] rowvector, colvector;

double[][] matrix;

Array Creation

Array objects, like other objects, are created with new. For example,

String[] arrayOfStrings = new String[10];

Another way to initialize array variables is

int[] arrayOf1To5 = { 1, 2, 3, 4, 5 };

String[] arrayOfStrings = { "array",

"of",

"String" };

Widget[] arrayOfWidgets = { new Widget(),

new Widget() };

Once an array object is created, it never changes length!

int[][] arrayOfArrayOfInt = {{ 1, 2 }, { 3, 4 }};

The array's length is available as a final instance variable length. For example,

int[] arrayOf1To5 = { 1, 2, 3, 4, 5 };

System.out.println(arrayOf1To5.length);

Array Accesses

All array accesses are checked at run time: An attempt to use an index that is less than zero or greater than or equal to the length of the array causes an IndexOutOfBoundsException to be thrown.

package genDict;

import genListFW.*;

/**
* An implementation of IDictionary<K, V> using an array to hold the
* DictPair<K, V>.
*
* @author Alan L. Cox
* @author Dung X. Nguyen ("generifier")
* @since 03/23/05
*/
public class DictArray<K, V> implements IDictionary<K, V> {
    /*
    * An array of DictPair<K, V> s ordered by key of type K.
    * K must extends or implements Comparable.
    */
    private int _firstEmptyPair = 0;
    private DictPair<K, V>[] _pairs = new DictPair[1];

    /**
    * Clears the contents of the dictionary leaving it empty.
    *
    * Implemented by replacing the existing array with a new,
    * empty one.
    */
    public void clear() {
        _firstEmptyPair = 0;
        _pairs = new DictPair[1];
    }

    /**
    * Returns true if the dictionary is empty and false otherwise.
    */
    public boolean isEmpty() {
        return _firstEmptyPair == 0;
    }

    public boolean isFull() {
        return _firstEmptyPair >= _pairs.length;
    }

    /**
    * Returns an IList of DictPairs corresponding to the entire
    * contents of the dictionary.
    */
    public IList< DictPair<K, V> > elements(final IListFactory< DictPair<K, V> > lf) {
        IList< DictPair<K, V> > l = lf.makeEmptyList();

        for (int i = _firstEmptyPair - 1; i >= 0; i--)
            l = lf.makeNEList(_pairs[i], l);

        return l;
    }

    /**
    * Binary Search Algorithm:
    * Returns either (1) the index of the key if it is stored
    * in the array or (2) the index of the next smaller key
    * if it is NOT stored in the array. (If there is NOT
    * a smaller key in the array, returns -1.)
    * Complexity Analysis is done in a latter section below.
    */
    private int findIndex(Comparable key) {
        int lo = -1;
        int hi = _firstEmptyPair;

        while (lo + 1 != hi) {
            int mid = (lo + hi)/2;
            int result = ((Comparable)_pairs[mid].getKey()).compareTo(key);

            if (result > 0) // _pairs[mid].getKey() > key
                hi = mid;
            else if (result == 0) // _pairs[mid].getKey() == key
                return mid;
            else // _pairs[mid].getKey() < key
                lo = mid;
        }
        return lo;
    }

    /**
    * Returns the DictPair with the given key. If there is not
    * a DictPair with the given key, returns null.
    *
    * Returns a DictPair rather than the value alone so that
    * the user can distinguish between not finding the key and
    * finding the pair (key, null).
    */
    public DictPair<K, V> lookup(K key) {
        int index = findIndex((Comparable)key);

        if ((index >= 0) &&
                ((Comparable)_pairs[index].getKey()).compareTo(key) == 0)
            return _pairs[index];

        return null;
    }

    /**
    * Inserts the given key and value. If the given key is already
    * in the dictionary, the given value replaces the key's old
    * value.
    */
    public void insert(K key, V value) {
        int index = findIndex((Comparable)key);

        if ((index >= 0) &&
                ((Comparable)_pairs[index].getKey()).compareTo(key) == 0) {
            _pairs[index] = new DictPair(key, value);
            return;
        }
        if (_firstEmptyPair == _pairs.length) {

            DictPair<K, V>[] newPairs = new DictPair[2*_pairs.length];

            for (int i = 0; i < _pairs.length; i++)
                newPairs[i] = _pairs[i];

            _pairs = newPairs;
        }
        int i = _firstEmptyPair;

        for (index++; i > index; i--)
            _pairs[i] = _pairs[i - 1];
        _pairs[i] = new DictPair(key, value);

        _firstEmptyPair++;
    }

    /**
    * Removes the DictPair with the given key and returns it.
    * If there is not a DictPair with the given key, returns
    * null.
    */
    public DictPair<K, V> remove(K key) {
        int index = findIndex((Comparable)key);

        if ((index >= 0) &&
                ((Comparable)_pairs[index].getKey()).compareTo(key) == 0) {

            DictPair<K, V> pair = _pairs[index];

            int i = index;

            for (_firstEmptyPair--; i < _firstEmptyPair; i++)
                _pairs[i] = _pairs[i + 1];
            _pairs[i] = null;

            return pair;
        }
        return null;
    }
}

Calculating the Computational Cost of `findIndex()`

Consider the following array and its possible traversals by findIndex().

In general, findIndex() examines at most ceil(log2(n+1)) keys, where n is the length of the array.

Can We Improve On Binary Search?

Consider an ordered, array-based IDictionary implementation, such as DictArray.
Suppose that keys are uniformly distributed.
How do you find a number in a phone book?

Specifically, if I asked you find ``Alan Cox'' in the phone book would you start in the middle?

Interpolation Search

Recall the findIndex() method, implementing binary search.
Rewrite mid = (lo + hi)/2 as mid = lo + (hi - lo)/2
Replace (hi - lo)/2 with an expression that places us closer to what we're looking for
mid = lo + ((key - keys[lo + 1])*(hi - lo))/(keys[hi - 1] - keys[lo + 1])
Note: The Comparable interface is insufficient for interpolation search.

Example

Consider the following array of elements: 9, 21, 32, 38, 51, 59, 68, 80, 91, 97, 113, 119, 131, 142, 149
How many steps would binary search require in order to find 68?
How many steps would interpolation search require in order to find 68?

`findIndex()`

Suppose that we used an extended Comparable interface that includes the method int sub(Object key)

private int findIndex(Comparable key) {
    int lo = -1;
    int hi = _firstEmptyKeyValuePair;
    while (lo + 1 != hi) {
        ExtendedComparable loKey = _pairs[lo + 1].getKey();
        ExtendedComparable hiKey = _pairs[hi - 1].getKey();
        int mid = lo + key.sub(loKey) * (hi - lo) / hiKey.sub(loKey);
        int result = _pairs[mid].getKey().compareTo(key);
        if (result == 0)
            return mid;
        else if (result > 0)
            hi = mid;
        else
            lo = mid;
    }
    return lo;
}

The Computational Cost of Interpolation Search

If the keys are uniformly distributed, the number of steps in an interpolation search is O(log log n).
If, instead, the keys are not uniformly distributed, e.g., 1, 2, 3, 4, 5, 6, 7, 8, 9, 999, and we search for 9, performance is poor.

Can you guarantee O(log n) worst case?

Comparing the three IDictionary implementations

		Expected-case Cost	Worst-case Cost

	lookup()	O(n) (i.e. some constant times n)	O(n)
DictLRS	insert()	O(n)	O(n)
	remove()	O(n)	O(n)

	lookup()	O(log n) (i.e. some constant times log n)	O(n)
DictBT	insert()	O(log n)	O(n)
	remove()	O(log n)	O(n)

	lookup()	O(log n)	O(log n)
DictArray	insert()	O(n)	O(n)
	remove()	O(n)	O(n)