All about Scott M Summers

Binary Search

I am having trouble with the Binary search for a string array. When my code calls binarySearch (line #43), I get an error:
Exception in thread "main" java.lang.RuntimeException: Uncompilable source code - missing return statement
at SearchSort.binarySearch(SearchSort.java:75)
at SearchSort.main(SearchSort.java:50)
Java Result: 1
Which I believe means that I need a return statement at the end of my while loop. But in the examples in my text book, and all the examples of binary search I've found online, there is not a return statement at the end of the while loop.

My Binary Search Code:

My Entire Code:

import java.util.Arrays;
import java.util.Scanner;
public class SearchSort {
private static final String[] NAMES = { "fred", "barney", "tom", "jerry", "larry", "moe", "curly",
"betty", "wilma", "bart", "homer", "marge", "maggie", "lisa", "pebbles", "bambam", "smithers",
"burns", "milhouse", "george", "astro", "dino", "mickey", "minnie", "pluto", "goofy", "donald",
"huey", "louie", "dewey", "snowwhite", "happy", "doc", "grumpy", "sneezy", "dopey", "sleepy",
"bambi", "belle", "gaston", "tarzan", "jane", "simba", "scar", "mufasa", "ariel", "flounder",
"bugs", "daffy", "elmer", "foghorn", "chickenhawk", "roger", "jessica", "hank", "bobby", "peggy",
"spot", "pongo", "perdy", "buzz", "potatohead", "woody", "chuckie", "tommy", "phil", "lil",
"angelica", "dill", "spike", "pepe", "speedy", "yosemite", "sam", "tweety", "sylvester", "granny",
"spiderman", "batman", "superman", "supergirl", "robin", "catwoman", "penguin", "thing", "flash", "silversurfer",
"xmen", "pokemon", "joker", "wonderwoman"};
private static String[]unSortedNames;
private static String[]sortedNames;
public static void main(String[] args) {
String nameToSearch;
boolean stopSearch;
int numberOfSearches = 0;
int comparisons;
int totalComparisons = 0;
int binaryComparisons;
do{
System.out.println("Enter a name to search for(type exit or quit to stop the program): ");
Scanner reader = new Scanner(System.in);
nameToSearch = reader.next();
switch (nameToSearch) {
case "quit":
System.out.println("Average of "+(totalComparisons/numberOfSearches)+" comparisons per linear search");
System.exit(0);
case "exit":
System.out.println("Average of "+(totalComparisons/numberOfSearches)+" comparisons per linear search");
System.exit(0);
default:
stopSearch = false;
break;
}
System.out.println("Searching for " + nameToSearch + "...\n");
comparisons = SearchSort.linearSearch(nameToSearch);
totalComparisons = (totalComparisons + comparisons + 1);
System.out.println("Linear search: Number of comparisons to find "+ nameToSearch + ": " + (comparisons+1));
binaryComparisons = SearchSort.binarySearch(nameToSearch);
System.out.println("Binary search: Number of comparisons to find "+ nameToSearch+": "+ (binaryComparisons+1));
numberOfSearches++;
}while(!stopSearch);
}
public static int linearSearch(String name){
int i;
for(i =0; i < NAMES.length; i++){
if(NAMES[i].equals(name)){
System.out.println(name + " is found in the array.");
break;
}
}
if(i == NAMES.length){
System.out.println(name + " not found in the array");
}
return i;
}
public static void copyArray(String[]source, String[]target){
unSortedNames=new String[NAMES.length]; //creates new unstored array.
System.arraycopy(NAMES, 0, unSortedNames, 0, NAMES.length); //copys NAMES array to new unsorted array.
sortedNames=new String[NAMES.length]; //creates new stored array.
System.arraycopy(NAMES, 0, sortedNames, 0, NAMES.length); //copys NAMES array to new sorted array.
Arrays.sort(sortedNames); //alphabetically sorts the sorted array.
}
public static int binarySearch(String name){
int numberOfElements = sortedNames.length;
int first = 0;
int last = numberOfElements-1;
int middle;
int binaryComparisons;
while(first <= last){
middle = (first + last)/2;
if(sortedNames[middle].equals(name)){
return middle; //found the name.
}
else if(first > last){
return numberOfElements; //can't find the name.
}
else{
int compare = sortedNames[middle].compareTo(name);
if(compare < 0){
first = middle + 1; //name is in the upper half of the array.
}
else if (compare > 0){
last = middle - 1; //name is in the lower half of the array.
}
}
}
}
}

Thanks for your time.

Scott M Summers

Recent posts by Scott M Summers