Build a BinarySearch class and a RecursiveBinarySearch class

Build a BinarySearch class and a RecursiveBinarySearch class that extends the superclass SearchAlgorithm

The binary search algorithm can be accomplished in a number of ways, but the basic algorithm is outlined below. You must implement this iteratively and recursaively

      LowIndex = 0

      HighIndex = arraySize – 1

      While LowIndex is less than or equal to HighIndex

            Set MidIndex to be equal to half way between the low and high index

            If the target word matches the word at MidIndex, return MidIndex (first case)

               If the target word is before the word at MidIndex, then set HighIndex to MidIndex - 1

               If the target word is after the word at MidIndex, then set LowIndex to MidIndex + 1

    If the target word was not found, throw an ItemNotFoundException (you create this class)

------Class SearchAlgorithm------

public abstract class SearchAlgorithm {

public abstract int search(String[] words, String wordToFind) throws ItemNotFoundException ;

private int count = 0;

public void incrementCount() {
count++;
}

public int getCount() {
return count;
}

public void resetCount() {

count = 0;
}}

-------Driver-------

import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Scanner;

public class BinSearchDriver {

   public final static String FILE_AND_PATH = \"longwords.txt\";

public static void main(String[] args) throws FileNotFoundException {
       Scanner input = new Scanner(new File(FILE_AND_PATH));
       int wordCount = 0;
       ArrayList theWords = new ArrayList();
  
       while(input.hasNext()) {
           theWords.add( input.next() );
           wordCount++;
       }

       String[] wordsToSearch = new String[theWords.size()];
       theWords.toArray(wordsToSearch);

tryBinarySearch(wordsToSearch, \"DISCIPLINES\");
       tryBinarySearch(wordsToSearch, \"TRANSURANIUM\");
       tryBinarySearch(wordsToSearch, \"HEURISTICALLY\");
       tryBinarySearch(wordsToSearch, \"FOO\");

       tryRecursiveBinarySearch(wordsToSearch, \"DISCIPLINES\");
       tryRecursiveBinarySearch(wordsToSearch, \"TRANSURANIUM\");
       tryRecursiveBinarySearch(wordsToSearch, \"HEURISTICALLY\");
       tryRecursiveBinarySearch(wordsToSearch, \"FOO\");

}

private static void tryBinarySearch(String[] wordsToSearch, String target) {
       SearchAlgorithm bs = new BinarySearch();
      
       try {
           System.out.print( target + \" found at index: \" + bs.search(wordsToSearch,target));
           System.out.println( \" taking \" + bs.getCount() + \" comparisons.\");
       }
       catch( ItemNotFoundException e ) {
           System.out.println( target + \":\" + e.getMessage());
       } }

private static void tryRecursiveBinarySearch(String[] wordsToSearch, String target) {

       SearchAlgorithm bs = new RecursiveBinarySearch();
      
       try {
           System.out.print( target + \" found at index: \" + bs.search(wordsToSearch,target));
           System.out.println( \" taking \" + bs.getCount() + \" comparisons.\");
       }
       catch( ItemNotFoundException e ) {
           System.out.println( target + \":\" + e.getMessage());
       }  
   }
  

Solution

public class BinarySearch extends SearchAlgorithm
{
   public int search(String[] words, String wordToFind) throws ItemNotFoundException
   {
       int lowIndex=0, highIndex=words.length-1, midIndex;
       while(lowIndex <= highIndex)
       {
           midIndex = (lowIndex + highIndex)/2;
           incrementCount();
           if(words[midIndex].compareTo(wordToFind) == 0)
               return midIndex;
           else if(words[midIndex].compareTo(wordToFind) > 0)
               highIndex = midIndex - 1;
           else
               lowIndex = midIndex + 1;
       }
       if(lowIndex >= highIndex)
           throw new ItemNotFoundException();
       return -1;
   }
}

public class RecursiveBinarySearch extends SearchAlgorithm
{
   int lowIndex, highIndex, midIndex;
   public int search(String[] words, String wordToFind) throws ItemNotFoundException
   {
       if(getCount() == 0)
       {
           lowIndex=0;
           highIndex=words.length-1;
       }
       midIndex = (lowIndex + highIndex)/2;
       incrementCount();
       if(lowIndex <= highIndex)
       {
           if(words[midIndex].compareTo(wordToFind) == 0)
               return midIndex;
           else if(words[midIndex].compareTo(wordToFind) > 0)
           {
               highIndex = midIndex - 1;
               return search(words, wordToFind);
           }
           else
           {
               lowIndex = midIndex + 1;
               return search(words, wordToFind);
           }
       }              
       else
           throw new ItemNotFoundException();
   }
}