BinarySearch.java

\/

import java.io.*; import java.util.*;

public class BinarySearch { public static void main(String[] args) { // Perform sample searches with strings String[] sortedFruits = { "Apple", "Apricot", "Banana", "Blueberry", "Cherry", "Grape", "Grapefruit", "Guava", "Lemon", "Lime", "Orange", "Peach", "Pear", "Pineapple", "Raspberry", "Strawberry" }; int sortedFruitsSize = sortedFruits.length; String[] fruitSearches = { "Nectarine", "Mango", "Guava", "Strawberry", "Kiwi", "Apple", "Raspberry", "Carrot", "Lemon", "Bread" }; int fruitSearchesSize = fruitSearches.length; int[] expectedFruitSearchResults = { -1, -1, 7, 15, -1, 0, 14, -1, 8, -1 }; StringComparer stringComparer = new StringComparer(); PrintSearches stringResults = new PrintSearches(); stringResults.print(sortedFruits, sortedFruitsSize, fruitSearches, fruitSearchesSize, stringComparer, expectedFruitSearchResults, true); // Perform sample searches with integers Integer[] integers = { 11, 21, 27, 34, 42, 58, 66, 71, 72, 85, 88, 91, 98 }; Integer[] integerSearches = { 42, 23, 11, 19, 87, 98, 54, 66, 92, 1, 14, 21, 66, 87, 83 }; int[] expectedIntegerSearchResults = { 4, -1, 0, -1, -1, 12, -1, 6, -1, -1, -1, 1, 6, -1, -1 }; IntComparer intComparer = new IntComparer(); PrintSearches integerResults = new PrintSearches(); integerResults.print(integers, integers.length, integerSearches, integerSearches.length, intComparer, expectedIntegerSearchResults, false); } }

\\\

StringComparer.java

\/

import java.util.*;

// StringComparer inherits from Comparator and so provides the // ability to compare two String objects. public class StringComparer implements Comparator { @Override public int compare(String a, String b) { return a.compareTo(b); } }

\\\

IntComparer.java

\/

import java.util.*;

// IntComparer inherits from Comparator and so provides the // ability to compare two integers. public class IntComparer implements Comparator { @Override public int compare(Integer a, Integer b) { return a - b; } }

\\\

Searcher.java

\/

import java.util.*;

public class Searcher { // Returns the index of the key in the sorted array, or -1 if the // key is not found. public static int binarySearch(T[] array, int arraySize, T key, Comparator comparer) { // Your code here return -1; } }

\\\

PrintSearches.java

\/

import java.util.*;

public class PrintSearches { public void print(T[] sortedArray, int sortedArraySize, T[] searchKeys, int searchKeysSize, Comparator comparer, int[] expectedResults, boolean keyInQuotes) { // If keyInQuotes is true, " characters surround the key in output // statements. Otherwise empty strings surround the key. String extra = keyInQuotes ? "\"" : ""; // Iterate through array of search keys and search for each for (int i = 0; i searcher = new Searcher(); int index = searcher.binarySearch(sortedArray, sortedArraySize, searchKey, comparer); // Compare actual result against expected int expected = expectedResults[i]; if (index == expected) { System.out.print("PASS: Search for key "); System.out.print(extra); System.out.print(searchKey); System.out.print(extra); System.out.print(" returned "); System.out.print(expected); System.out.print("."); System.out.print(" "); } else { System.out.print("FAIL: Search for key "); System.out.print(extra); System.out.print(searchKey); System.out.print(extra); System.out.print(" should have returned "); System.out.print(expected); System.out.print(", but returned "); System.out.print(index); System.out.print("."); System.out.print(" "); } } } }

Implement the Searcher class's binarySearch() generic method in the Searcher.java file. Access Searcher.java by clicking on the orange arrow next to BinarySearch.java at the top of the coding window. The method performs a binary search on the sorted array (first parameter) for the key (third parameter). binarySearch( ) returns the key's index if found, 1 if not found. Compare an array element to the key using the compare() method of the comparer object passed as binarySearch()'s last parameter. comparer. compare (a,b) returns an integer: - greater than 0 if a>b - less than 0 if a