DictionaryBinarySearch.java

public class DictionaryBinarySearch {

    /**
     * Binary search algorithm to find a target string in a sorted dictionary.
     * This assumes there is an index array of entries that maps each definition in the dictionary to its index.
     * For example, if the index array is {"CPU", "hard drive", "keyboard", "logic", "mouse", "NIC", "printer"},
     *     "Logic" is at index[3], and
     *     "Computer logic is an aspect of computer design concerning the fundamental operations and structures
     *     upon which all computer systems are built." will be at dictionary[3].
     * The number in [brackets] is the element number of the array, starting with 0.
     *
     * @param index An array of strings that map to their corresponding index in the dictionary.
     * @param dictionary An array of strings that are the definitions of the dictionary.
     * @param searchTerm The term to search for in the dictionary.
     * @return The dictionary entry corresponding to the index entry if found, or "Not found" if not found.
     */
    // The public static String stuff is all Java-ese. You can treat it as function binarySearch with two String arrays
    //     inputted, (the index and the dictionary) and a String (the search term).
    //     It will return a String with the definition, or that the term was not found.
    public static String binarySearch(String[] index, String[] dictionary, String searchTerm) {

        // Starts at the first element of the array (which is 0 in the computer world) and ends at the last element
        // (which is the length of the array - 1 in the computer world, because the array starts with 0).
        int start = 0;
        int end = index.length - 1;

        // The while loop will continue until either the search term is found, or there is no array left to search.

        while (start <= end) {

            // Divide the array into two halves based on the middle index.
            // In Java, since mid is an integer, the division will round down to the nearest integer.
            int mid = (start + end) / 2;

            System.out.printf("Midpoint term: %s%n", index[mid]);

            // This will convert acronyms like "NIC" to "nic." This is required because compareTo() treats "NIC"
            //     as less than "keyboard" because of the capitalization of the first letter in "NIC"
            //     and would split the wrong half.
            String indexTerm = index[mid].toLowerCase();

            // Does the middle index entry match the search term? If so, return the corresponding dictionary entry.
            if (indexTerm.equalsIgnoreCase(searchTerm)) {
                return dictionary[mid];
            }

            // If end is 0 or start is the last element and did not match the search term, break out of the loop.
            if (end == 0 || start == index.length - 1){
                break;
            }

            // If the search term was not found, discard the half of the array that will not contain the search term.
            // The compareTo() method in Java returns a negative number if the first string is numerically using Unicode
            //     before the second, and a positive number if the first string is numerically using Unicode after
            //     the second.
            // That's how we decide which half to discard.
            if (index[mid].compareTo(searchTerm) < 0) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }

            // The while loop continues until the search term is found or there is no array left to search.
            // The return keyword will break out of the loop.
        }

        // If the while loop completes without finding the search term, return "Not found".
        return "Not found";
    }
}