Advanced Programming Techniques (2011, 2013)

1. Arrays

1

An array is a collection of variables where each variable has the same data type, for example, an array of integers or an array of Appliance objects. Each variable in an array is called an element and has an index, also called the subscript, which denotes that element’s location within the array. One advantage of using arrays is that all the elements within an array can be declared, created, and passed to a function as a whole. However, each element may still be accessed individually by using the element’s index. Figure 1 shows a representation of an array with 10 elements. Notice that each element has a unique index, and the first index of an array is 0.

Figure 1: A representation of an array showing the elements and indices.

Fill an Array

It is often desirable to have the computer initialize all the elements in an array to a single value (usually zero). We do this by writing a statement that assigns a value to one element in the array, and then put that assignment statement inside a loop. If the array has n elements in it, then the loop causes the computer to repeat the assignment statement n times, once for each element in the array.

Example 1

/** Fills an array with the value x. */

public static void fill(double[] list, double x) {

for (int i = 0; i < list.length; ++i) {

list[i] = x;

}

}

Within the Java 1.7 libraries, there is already a fill method in the java.util.Arrays class. It is written almost exactly as shown above.

2

Initialize an Array to a Ramp

Figure 2: A plot of constantly increasing values forming a discrete ramp function.

Within programs that perform image processing, we often use an array as a palette. To get the color value to display for a pixel, the computer reads a pixel value from the image and then looks up that value in the palette. Then the computer displays the color from the palette at the corresponding pixel location on the monitor. Often the palette must be initialized to contain values that are constantly increasing, for example: 0, 1, 2, 3… This is known as a ramp because if you plotted the values in the array, you would see a sloping line or ramp, constantly increasing to the right as shown in figure 2.

Here is a code example showing how to initialize an array to an increasing ramp.

Example 2

/** Fills list with constantly increasing

* values from 0 to list.length - 1, inclusive. */

public static void ramp(int[] list) {

for (int i = 0; i < list.length; ++i) {

list[i] = i;

}

}

Figure 3: A plot of constantly decreasing values forming a discrete reverse ramp function.

Occasionally we want to initialize an array to hold constantly decreasing values such as: 15, 14, 13, … 0. This is known as a reverse ramp because if you plotted the values in the array, you would see a sloping line or ramp, constantly decreasing to the right as shown in figure 3. Example code to initialize an array to a reverse ramp is shown below.

3

Example 3

/** Fills list with constantly decreasing

* values from list.length - 1 to 0, inclusive. */

public static void reverseRamp(int[] list) {

int high = list.length - 1;

for (int i = 0; i < list.length; ++i) {

list[i] = high - i;

}

}

Reverse an Array

Reversing the order of the elements in an array is not commonly used in computer programs. However, it is an interesting operation, and understanding it helps students to understand more commonly used array operations. One way to reverse the elements in an array is to use two index variables: one index starts at the beginning of the array, and the other starts at the end of the array. Then write a loop that repeats n / 2 times where n is the number of elements in the array. Each time through the loop, the computer switches one element in the left half of the array with one element in the right half.

Example 4

/** Reverses the contents of an array. */

public static void reverse(float[] list) {

int left = 0;

int right = list.length - 1;

while (left < right) {

// Exchange two elements.

float swap = list[left];

list[left] = list[right];

list[right] = swap;

// Move the indices toward the center.

left++;

right--;

}

}

4

Rotate an Array

Rotating the elements of an array is also not commonly used in most programs, but is useful to help us study arrays. Rotating the elements of an array one position to the left is easily done by storing the first element in a temporary variable, moving all the other elements one position to the left, and then copying the value from the temporary variable to the last position in the array.

Example 5

/** Rotates the elements of an

* array one position to the left. */

public static void rotateLeft(float[] list) {

int last = list.length - 1;

float swap = list[0];

for (int i = 0; i < last; ++i) {

list[i] = list[i + 1];

}

list[last] = swap;

}

Rotating the elements of an array to the right can be done similarly to rotating to the left except moving each element to the right is done from the end of the array to the beginning.

Example 6

/** Rotates the elements in an

* array one position to the right. */

public static void rotateRight(float[] list) {

int last = list.length - 1;

float swap = list[last];

for (int i = last; i > 0; --i) {

list[i] = list[i - 1];

}

list[0] = swap;

}

5

Before rotating

After rotating

Figure 4: Rotating an array of 6 elements two positions to the right forms 2 groups of 3 elements each.

Rotating the elements of an array by more than one position forms groups of elements that trade positions with one another. The number of groups is always the greatest common divisor of the number of positions to rotate and the array length. For example, rotating an array of length 6 two positions to the right forms 2 groups of 3 elements that trade positions as shown in figure 4.

Example 7

/** Rotates the elements of an array by k positions.

* Negative values of k rotate to the left.

* Positive values rotate to the right. */

public static void rotate(float[] list, int k) {

int n = list.length;

k %= n;

if (k < 0) { // rotate left

k = -k;

}

else if (k > 0) { // rotate right

k = n - k;

}

else { // no rotation

return;

}

int groups = gcd(k, n);

for (int group = 0; group < groups; group++) {

int one = group;

int two;

float save = list[one];

while ((two = (one + k) % n) != group) {

list[one] = list[two];

one = two;

}

list[one] = save;

}

}

6

Example 8

/** Finds and returns the greatest

* common divisor of two integers. */

private static int gcd(int a, int b) {

// Ensure a and b are not negative.

a = Math.abs(a);

b = Math.abs(b);

// Loop until the greatest common divisor is found.

int r; // Holds the remainder

do {

r = a % b;

a = b;

b = r;

} while (r != 0);

return a;

}

It is interesting to note that we don’t need to actually rotate the elements of an array in order to process the elements in a rotated order. Consider this code that prints the elements of an array in a rotated order without ever rotating the array.

Example 9

/** Prints the elements in an array in a rotated order

* without actually rotating the contents of the array.

* Negative k causes printing with a left rotation.

* Positive k causes printing with a right rotation. */

public static void printRotated(float[] list, int k) {

System.out.print('[');

final int n = list.length;

int index = -(k % n);

if (index < 0) {

index += n;

}

String separator = "";

for (int i = 0; i < n; ++i) {

System.out.print(separator);

separator = ", ";

System.out.print(list[index]);

if (++index == n) {

index = 0;

}

}

System.out.println(']');

}

7

Linear Search

Very often a computer program must determine if a certain value is stored in an array or not and if stored in the array, then return the value’s location. The value to be found is called the key. If the array is not too large (perhaps less than 100 elements), finding the key can be easily done using a linear search. A linear search is done by comparing each element in the array with the key until the key is found in the array or the end of the array is reached.

The advantage of a linear search is that it is simple and easy to code. The disadvantage is that it is too slow if the array has many elements in it. When the array has many elements in it, it is likely faster to sort the array and keep it sorted and to use a binary search to find the key within the array.

Java code to perform a linear search is shown below. In the example, if the key is found in the array, the search function returns the index of the location within the array where the key was found. If the key is not found, the search function returns −1.

Example 10

/** If key is in list, returns the first index where

* key is located within list; otherwise returns -1. */

public static int linearSearch(double[] list, double key) {

for (int i = 0; i < list.length; ++i) {

if (list[i] == key) {

return i;

}

}

return -1;

}

Binary Search

If the elements in an array are sorted, then the computer can use a faster algorithm called binary search to find an element within that array. The binary search algorithm works by comparing the key to the middle most element in the array. If the key is greater than the middle most element, then the search is repeated in the last half of the array. If the key is less than the middle most element, then the search is repeated in the first half of the array. Of course, if the key is equal to the middle most element, then the key has been found and the search is done. This process of comparing the key to the middle most element of the current interval is repeated until the key is found or the interval has shrunk to only one element. If that one element is not the same as the key, then the key is not present in the array, and the function below returns a negative value.

8

Example 11

/** If key is in list, returns any index where key is

* located within list; otherwise returns -insertPoint - 1.

* Assumes list is already sorted. */

public static int binarySearch(float[] list, float key) {

int left = 0;

int right = list.length - 1;

while (left <= right) {

int mid = left + ((right - left) >>> 1);

float cmp = key - list[mid];

if (cmp > 0) {

left = mid + 1;

}

else if (cmp < 0) {

right = mid - 1;

}

else {

return mid;

}

}

// key is not present in list, but if it

// were, it would be stored at location left.

return -(left + 1);

}

If the key is not present in the array, the return value of the binary search function above is −insertPoint − 1. In other words, if the key is not present in the array, the index where key should be inserted can be found using this code:

int index = binarySearch(list, key);

if (index < 0) {

int insertPoint = -index - 1;

}

9

In the binarySearch code above, the statement that computes mid needs some explanation. Here is the line:
mid = left + ((right - left) >>> 1);
The unsigned right shift operator (>>>) shifts all the bits in an integer to the right which is the same as using integer division to divide a non-negative integer by a power of two. However, the right shift operator executes faster than integer division. To help us understand the statement, we can rewrite it by replacing >>> 1 with / 2.
mid = left + (right - left) / 2;
Notice that this statement uses integer division to truncate (not round) the result of the division. Also notice that if this were an algebraic expression, it could be simplified to
mid = (left + right) / 2;
which is easier to understand. From this simplified formula we see that the midpoint is simply the left index plus the right index divided in half. However, because an array in Java can have as many as 2,147,483,647 (2³¹ − 1)elements, and that is also the largest number that an int can hold, we must use the more complex formula.

To understand why we must use the more complex formula, imagine an array with just slightly more than 2³⁰ elements, say 1,073,741,829 (2³⁰ + 5), a little more than 1 gigabyte of elements. Now imagine that the computer is nearing the end of its binary search for some value that is located near the end of the array. What happens with our simplified formula when left = 1,073,741,821 and right = 1,073,741,828? You and I can add those two numbers together to get 2,147,483,649. However, that sum is larger than the largest value that a Java int can hold. So when the computer adds those two numbers together the 32-bit int in the computer’s CPU overflows, and the computer gets the sum of −1,073,741,823. Yes, that’s right, the computer adds two large positive numbers together and gets a negative number as a result. This is known as overflow. Obviously the negative sum is incorrect, and even after it is divided by 2 (see the simplified formula above), it will still be negative and will still cause an ArrayIndexOutOfBoundsException. So, we must use the more complex formula.

Within the Java 1.7 libraries, there is an existing binary search function in the java.util.Arrays class. However, as of Java 1.7 it still uses the simple expression for computing the middle index between left and right:
mid = (left + right) >>> 1
which is a bug.

10

Find a Range

Sometimes a computer program has a list of numerical ranges and must find the range that contains some value. Examples of this type of computing problem include:

· determining a person’s income tax rate from a list of income ranges and graduated tax rates

· determining a customer’s discount rate from a list of purchase ranges and discount rates

· determining a salesperson’s commission from a list of sales ranges and commission rates

· determining a student’s letter grade from a list of score ranges and letter grades

For example, a company may offer discounts to its customers where the discount rate is based on the amount purchased according to this table.

A beginning programmer will often code a Java solution to this problem like this:

Example 12

/** Computes and returns a discounted purchase amount. */

static double getDiscountedAmount(double purchase) {

double rate = 0;

if (purchase >= 0 && purchase < 300) {

rate = 0;

}

if (purchase >= 300 && purchase < 600) {

rate = 0.02;

}

if (purchase >= 600 && purchase < 1000) {

rate = 0.025;

}

if (purchase >= 1000) {

rate = 0.03;

}

double discount = purchase * rate;

return purchase - discount;

}

11

After a little practice, the beginning programmer realizes that the separate if statements can be connected with else and that the else part of each if statement will be executed only when the previous if part is false. This means the code can be written more succinctly and achieve exactly the same results by removing the left half of each if statement.

Example 13

/** Computes and returns a discounted purchase amount. */

static double getDiscountedAmount(double purchase) {

double rate;

if (purchase < 300) {

rate = 0;

}

else if (purchase < 600) {

rate = 0.02;

}

else if (purchase < 1000) {

rate = 0.025;

}

else {

rate = 0.03;

}

double discount = purchase * rate;

return purchase - discount;

}

The problem with both these solutions is that if the company changes the purchase amount ranges or the discount rates, then a programmer must change the corresponding code. An improved solution is to remove the ranges and rates from the code and place them in a file or database so that the computer can read them into an array or arrays when it runs the program. Then the programmer must write a simple linear or binary search to find the correct range and the corresponding discount rate as shown in the next example.

Example 14

// The values in these arrays can be hard coded

// into your program, or even better, they can be

// read from a file or database.

static final double[] limits = { 300, 600, 1000 };

static final double[] rates = { 0, .02, .025, .03 };

/** Computes and returns a discounted purchase amount. */

static double getDiscountedAmount(double purchase) {

int i;

for (i = 0; i < limits.length; ++i) {

if (purchase < limits[i]) {

break;

}

}

double rate = rates[i];

double discount = purchase * rate;

return purchase - discount;

}

12

Table Based Solutions

A programming solution like the previous one is known as a table based solution because tables of data are stored in arrays instead of being stored in the code inside if statements. A table based solution is almost always shorter and less complex than a corresponding solution that doesn’t use tables. Consider the following code that creates a number pad for a Java Swing graphical user interface.

Example 15

private static JPanel makeNumberPad() {

JButton btnZero = new JButton("0");

JButton btnOne = new JButton("1");

JButton btnTwo = new JButton("2");

JButton btnThree = new JButton("3");

JButton btnFour = new JButton("4");

JButton btnFive = new JButton("5");

JButton btnSix = new JButton("6");

JButton btnSeven = new JButton("7");

JButton btnEight = new JButton("8");

JButton btnNine = new JButton("9");

JPanel numberPad = new JPanel(new GridLayout(4, 3));

numberPad.add(btnSeven);

numberPad.add(btnEight);

numberPad.add(btnNine);

numberPad.add(btnFour);

numberPad.add(btnFive);

numberPad.add(btnSix);

numberPad.add(btnOne);

numberPad.add(btnTwo);

numberPad.add(btnThree);

numberPad.add(btnZero);

return numberPad;

}

Now consider this much shorter solution that creates the same number pad but uses a table of Strings to hold the text for all buttons and a loop to create all ten buttons.

Example 16

private static JPanel makeNumberPad() {

String[] buttonTexts = {

"7", "8", "9",

"4", "5", "6",

"1", "2", "3",

"0"

};

JPanel numberPad = new JPanel(new GridLayout(4, 3));

for (int i = 0; i < buttonTexts.length; i++) {

JButton button = new JButton(buttonTexts[i]);

numberPad.add(button);

}

return numberPad;

}

13

The table based solution (second example) is preferred because it requires less code. Less code is almost always easier to write, read, and understand, and it usually has fewer mistakes because there is simply less code to contain the mistakes.

Roman Numerals

When you are writing table based solutions, quite often a single table can be used in more than one function. The next function uses a table of Strings stored as a two-dimensional array to convert an Arabic number to Roman numerals. The function after uses the same table to perform the opposite conversion.

Example 17

/** The data table used to convert Arabic

* numbers to Roman numerals and vice versa. */

private static final String[][] numerals = {

{ "", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX" },

{ "", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC" },

{ "", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM" },

{ "", "M", "MM", "MMM" }

};

/** Converts a base 10 Arabic number to Roman numerals. */

public static String romanFromArabic(int arabic) {

assert 0 <= arabic && arabic < 4000;

String roman = "";

int divisor = 1000;

// Count down from the thousands

// column (3) to the ones column (0).

for (int exponent = 3; exponent >= 0; exponent--) {

// Extract one Arabic digit.

int digit = arabic / divisor;

// Look up the corresponding Roman pattern

// and concatenate it to the Roman numerals.

roman += numerals[exponent][digit];

// Subtract the digit from the Arabic number.

arabic -= digit * divisor;

// Prepare the divisor for the next column.

divisor /= 10;

}

return roman;

}

14

Example 18

/** Converts Roman numerals to a base 10 Arabic number. */

public static int arabicFromRoman(String roman) {

int arabic = 0;

// Count down from the thousands

// column (3) to the ones column (0).

for (int exponent = 3; exponent >= 0; exponent--) {

// The longest possible "single digit" Roman

// pattern has 4 characters, e.g.VIII

int length = Math.min(roman.length(), 4);

for (; length > 0; length--) {

// Extract characters from the Roman number.

String chars = roman.substring(0, length);

// Find the extracted characters using linear search.

int digit = linearSearch(numerals[exponent], chars);

if (digit >= 0) {

arabic += digit * Math.pow(10, exponent);

roman = roman.substring(length);

break;

}

}

}

return arabic;

}

15

Sort an Array

The best way to sort an array is to use the sort functionality provided by the programming language that you are using because this built in sorting functionality has been optimized and tested. Java includes built in sort functionality which is in the java.util.Arrays class. Here is Java code to sort an array using the built in functionality.

Example 19

String[] list = { "Radish", "Carrot", "Tomato", "Pea" };

java.util.Arrays.sort(list);

In Java, if you wish to sort objects created from your own class, then you must implement and create a Comparator object and pass that Comparator object as the second parameter to Arrays.sort. The sort function will call thecompare function in the Comparator object to compare two objects and the compare function will return one of the

· a negative integer if the first object should be placed before the second in the sorted array

· a zero (0) if the contents of the two objects are equal

· a positive number if the first object should be placed after the second in the sorted array

Then the sort function will switch the location of the two objects if necessary and repeat this process many times for all elements until the entire array is sorted.

This Java code shows how to sort Student objects by name and by age using two different Comparator objects.

Example 20

import java.util.Arrays;

import java.util.Comparator;

public class Student {

private String name;

private int age;

public Student(String name, int age) {

this.name = name;

this.age = age;

}

@Override

public String toString() {

return name + " " + age;

}

16

/** A Comparator used when sorting Students by name. */

static class NameComptor implements Comparator<Student> {

@Override

public int compare(Student s1, Student s2) {

int r = s1.name.compareTo(s2.name);

// If two students have the same

// name, order them by their ages.

if (r == 0) {

r = s1.age - s2.age;

}

return r;

}

}

/** A Comparator used when sorting Students by age. */

static class AgeComptor implements Comparator<Student> {

@Override

public int compare(Student s1, Student s2) {

int r = s1.age - s2.age;

// If two students have the same

// age, order them by their names.

if (r == 0) {

r = s1.name.compareTo(s2.name);

}

return r;

}

}

public static void main(String[] args) {

Student[] students = {

new Student("Jane", 18),

new Student("Sam", 17),

new Student("Nigel", 14)

};

System.out.println(Arrays.toString(students));

// Sort the students by name.

Arrays.sort(students, new NameComptor());

System.out.println(Arrays.toString(students));

// Sort the students by age.

Arrays.sort(students, new AgeComptor());

System.out.println(Arrays.toString(students));

}

}

17

You might be wondering how a sort function works. There are many different, well known sort algorithms (selection, exchange, insertion, heap, quick, etc.). They all work by repeatedly comparing elements in an array to other elements in the array and simply moving the elements around within the array. Shown below is Java code to sort an array using the insertion sort algorithm. Insertion sort is a simple and reasonably fast algorithm, although it is usually not as fast as the quick sort algorithm.

Example 21

/** Sorts the contents of an array in ascending

* order using the insertion sort algorithm. */

public static void sort(double[] list) {

int first = 0;

int last = list.length - 1;

for (int i = last - 1; i >= first; --i) {

double swap = list[i];

int j;

for (j = i + 1; j <= last; ++j) {

if (swap <= list[j]) {

break;

}

list[j - 1] = list[j];

}

list[j - 1] = swap;

}

}

18

Possible User Input

Most computer programs require user input. User friendly programs maintain a list of possible input values. As the user enters input, these programs show a list of possible values, allowing the user to choose from the list which dramatically reduces the user effort required to enter the input. I call this style of gathering input possible user input, and it can be implemented with a sorted list of possible input terms and a binary search as shown in the following code examples.

Notice that the findAnyCandidate function uses binary search to find any term that starts with the user entered prefix. Then the findCandidates function performs two secondary searches to find the first and last terms that start with that prefix. I chose linear search for the two secondary searches in findCandidates because the list of possible terms is usually too small to merit using the more complex binary search.

The function startsWithCompare is used during the binary search and is somewhat unusual because it determines if a possible term starts with a user entered prefix or if not, if the prefix should come before or after the term. In other words, this comparison function is a combination of the Java String.startsWith and String.compareTo functions.

/** A Bounds object holds the index of the first and

* last values in a list that start with a prefix. */

public class Bounds {

public int first, last;

public Bounds(int first, int last) {

this.first = first;

this.last = last;

}

}

19

Example 22

/** Returns the indexes of the first and last items

* in candidates that start with prefix; returns null

* if no item in candidates starts with prefix. */

public static Bounds findCandidates(String prefix, String[] candidates) {

Bounds bounds = null;

// Find any item that starts with prefix.

int index = findAnyCandidate(prefix, candidates);

if (index >= 0) {

// Find the first item that starts with prefix.

int first = index;

while (--first >= 0) {

if (!candidates[first].startsWith(prefix)) {

break;

}

}

first++;

// Find the last item that starts with prefix.

int last = index;

while (++last < candidates.length) {

if (!candidates[last].startsWith(prefix)) {

break;

}

}

last--;

bounds = new Bounds(first, last);

}

return bounds;

}

20

Example 23

/** Returns the index of any item in candidates that starts

* with prefix; returns -1 if no such item exists. */

private static int findAnyCandidate(String prefix, String[] candidates) {

int left = 0;

int right = candidates.length - 1;

while (left <= right) {

int mid = left + ((right - left) >>> 1);

String term = candidates[mid];

int cmp = startsWithCompare(prefix, term);

if (cmp > 0) {

left = mid + 1;

}

else if (cmp < 0) {

right = mid - 1;

}

else {

return mid;

}

}

return -1;

}

Example 24

/** Returns 0 if term starts with prefix; otherwise

* returns a negative integer if prefix should come

* before term and a positive integer if prefix

* should come after term in their normal ordering. */

private static int startsWithCompare(String prefix, String term) {

int preLen = prefix.length();

int minLen = Math.min(preLen, term.length());

for (int i = 0; i < minLen; ++i) {

int diff = prefix.charAt(i) - term.charAt(i);

if (diff != 0) {

return diff;

}

}

return preLen == minLen ? 0 : prefix.charAt(minLen);

}

21

Predictive User Input

Some programs are even smarter and not only maintain a list of possible input values but also a count of how often the user has entered each value. Storing the count enables the program to predict which of the possible values the user is entering. As the user types, the program shows a list of possible values, but the default value is the value that starts with the text the user has entered and has been used most often. This allows the user to enter frequently used values even more quickly, and is known as predictive user input.

Figure 5 is a screen shot of Ledger 2011, a financial application written using Microsoft Access that employs predictive user input when a user is entering payees, categories, and other information. Notice that the user is entering the data for check #2016 written to the Madison School Lunch program and has typed “Mad” in the Payee column. Because Ledger employs predictive user input for payees, Ledger has predicted that the user is entering “Madison School Lunch” instead of “Madison County” even though Madison County comes before Madison School Lunch in alphabetical order. Ledger predicted Madison School Lunch because the user has entered it more often than she has entered Madison County.

Figure 5: Screen shot of Ledger 2011, a financial application that uses predictive user input. When the user typed “Mad”, Ledger predicted Madison School Lunch instead of Madison County because the user has entered Madison School Lunch more often than Madison County.

Here is the Java source code that implements predictive user input to predict which value a user is entering.

/** An Entry holds both a possible input value and the

* number of times that value has been entered by a user. */

class Entry {

public String term;

public int uses; // Number of times term has been used

public Entry(String term, int uses) {

this.term = term;

this.uses = uses;

}

22

@Override

public String toString() {

return term + ", " + uses;

}

}

Example 25

/** Returns the location of the most frequently used

* term in candidates that starts with prefix. */

public static int findBestCandidate(String prefix, Entry[] candidates) {

int index = findAnyCandidate(prefix, candidates);

if (index >= 0) {

int max = candidates[index].uses;

int save = index;

// Find the first item that starts with prefix, and

// simultaneously find the item between the first

// and the one at save that has been used the most.

int i = save;

while (--i >= 0) {

if (candidates[i].term.startsWith(prefix)) {

int freq = candidates[i].uses;

if (freq >= max) {

max = freq;

index = i;

}

}

else {

break;

}

}

// Find the last item that starts with prefix, and

// simultaneously find the item between the first

// and the last one that has been used most often.

i = save;

while (++i < candidates.length) {

if (candidates[i].term.startsWith(prefix)) {

int freq = candidates[i].uses;

if (freq > max) {

max = freq;

index = i;

}

}

else {

break;

}

}

}

return index;

}

23

Example 26

/** Returns the index of any item in candidates that starts

* with prefix. Returns -1 if no such item exists. */

private static int findAnyCandidate(String prefix, Entry[] candidates) {

int left = 0;

int right = candidates.length - 1;

while (left <= right) {

int mid = left + ((right - left) >>> 1);

String term = candidates[mid].term;

int cmp = startsWithCompare(prefix, term);

if (cmp > 0) {

left = mid + 1;

}

else if (cmp < 0) {

right = mid - 1;

}

else {

return mid;

}

}

return -1;

}

Programming Exercises

1. Rewrite the getDiscountedAmount function in example 14 to use a binary search to find the correct range instead of a linear search.

2. Download, install, and use Ledger 2011 to really understand how much easier it is to enter data when the computer correctly predicts what you are trying to enter.