Build a BinarySearch class and a RecursiveBinarySearch class that extends the su

ID: 3938650 • Letter: B

Question

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());
       }
   }

Explanation / Answer

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();
   }
}

Navigate

Build a Binary Search Tree in C++. Do not use an STL. Allow the user to enter an

Build a C++ application that will accept input from users for a total number of

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

Build a BinarySearch class and a RecursiveBinarySearch class that extends the su

Question

Explanation / Answer

Related Questions

Navigate