Searching and Sorting - Building Java Programs: A Back to Basics Approach - page 800

If we want to do a binary search on objects, the objects must have an ordering (in
other words, must be of a type that implements the Comparable interface or must be
provided with a comparator) and the elements in the array or collection must be in
sorted order. One common example would be an array of String s. Since we can't
use relational operators like < and >= on objects, we must call the compareTo method
on pairs of String objects and examine the value it returns. The following code
implements a binary search on an array of String s:

// Binary search algorithm that works with Strings.
// Returns the index at which the given target String
// appears in the given input array, or -1 if not found.
// pre: array is sorted
public static int binarySearch(String[] strings, String target) {
int min = 0;
int max = strings.length - 1;
while (min <= max) {
int mid = (max + min) / 2;
int compare = strings[mid].compareTo(target);
if (compare == 0) {
return mid; // found it!
} else if (compare < 0) {
min = mid + 1; // too small
} else { // compare > 0
max = mid - 1; // too large

}

}
return -1; // not found

}

Selection Sort
Selection sort is a well-known sorting algorithm that makes many passes over an
input array to put its elements into sorted order. Each time it runs through a loop, it
selects the smallest value and puts it in the proper place near the front of the array.
Consider the following array:

int[] nums = {12, 123, 1, 28, 183, 16};

0 1 2 3 4 5

12 123 1 28 183 16

How would you put its elements into order from smallest to largest? The selection
sort algorithm conceptually divides the array into two pieces: sorted elements at the
front and unsorted elements at the end. The first step of the selection sort makes a
pass over the array and finds the smallest number. In the sample array, the smallest is
nums[2] , which equals 1 . The algorithm then swaps the smallest value with the value