Sorting, Searching, and Merging - Advanced Topics in Java: Core Concepts in Data Structures - page 18

We can test binarySearch with Program P1.5.
Program P1.5
public class BinarySearchTest {
public static void main(String[] args) {
int[] num = {17, 24, 31, 39, 44, 49, 56, 66, 72, 78, 83, 89, 96};
int n = binarySearch(66, num, 0, 12);
System.out.printf("%d\n", n); //will print 7; 66 in pos. 7
n = binarySearch(66, num, 0, 6);
System.out.printf("%d\n", n); //will print -1; 66 not in 0 to 6
n = binarySearch(70, num, 0, 12);
System.out.printf("%d\n", n); //will print -1; 70 not in list
n = binarySearch(89, num, 5, 12);
System.out.printf("%d\n", n); //will print 11; 89 in pos. 11
} //end main
// binarySearch goes here
} //end class BinarySearchTest
When run, the program will print the following:
7
-1
-1
11
1.7 Searching an Array of Strings
We can search a sorted array of strings (names in alphabetical order, say) using the same technique we used for
searching an integer array. The major differences are in the declaration of the array and the use of the String function
compareTo , rather than == or < , to compare two strings. The following is the string version of binarySearch :
public static int binarySearch(String key, String[] list, int lo, int hi) {
//search for key from list[lo] to list[hi]
//if found, return its location; otherwise, return -1
while (lo <= hi) {
int mid = (lo + hi) / 2;
int cmp = key.compareTo(list[mid]);
if (cmp == 0) return mid; // search succeeds
if (cmp < 0) hi = mid -1; // key is 'less than' list[mid]
else lo = mid + 1; // key is 'greater than' list[mid]
}
return -1; //lo and hi have crossed; key not found
} //end binarySearch
Since we need to know whether one string is equal to, or less than, another, it is best to use the compareTo
method.