String Binary Search
Back to the Program-A-Day homepage
ProblemYou are given an ordered array of Strings. Write a program that will analyze the array using binary search. The first thing your program should be able to do is verify that the array is indeed ordered. This will be done in a separate method, and the method will return a boolean value ('true' indicating that the array is ordered). Second, if the array is ordered, then you must prompt the user to guess a word that might be in the array. This prompt will be done with JOptionPane. You will need another method to conduct a binary search in the array to look for the user's guess. This method will also return a boolean indicating success or failure. Finally, the user will only be allowed to guess a maximum of five times before the program will stop. For your output, the program will first print the array followed by the sorted status of the array (whether it is ordered or not). Then it will print out every guess the user makes. Finally, print out the user's number of attempts and whether they succeeded in entering a word that's in the array. Your output should look something like this: Array: "word1" "word2" "word3" It is ordered. Guess 1: blah Guess 2: blah Guess 3: word1 The array contains "word1". It took you 3 attempt(s) to get it. |
Problem Solving and Programming Examples
| |
|---|---|---|
SolutionLet's start by putting together the main method. When starting to write any section of code, we need to figure out what variables we will be using. We will need: one integer variable to store the maximum number of tries a user can guess; three boolean values, one to track whether the array is ordered or not, one to track whether the user has reached the max number of attempts, and one to track whether they entered a guess that was in the array; a String to hold the input entered by JOptionPane; another integer to track the number of attempts made by the user; and finally, our ordered array of Strings. We'll place these at the top of our main method. Remember to always initialise your variables! final int MAX_TRIES = 5;
boolean done = false;
boolean found = false;
boolean inOrder = false;
String input = "";
int count = 0;
String [] ordered = {"a","cake","is","lie","the"};
Notice I used "final" and all caps for the maximum tries variable. That's because that number is a constant and will never change. Now, the problem stated that we need to print out the array's contents from a method. Create a make the call to this non-existent method. At this point, you can either jump ahead and write the body for this method, or continue writing out the main method. While either strategy is fine, keep in mind that when writing an exam you will be doing so in pencil. If you don't leave yourself enough room, jumping ahead to write a method might cause you to not leave enough room for the main method. I always like to write out a method as much as possible before going to the next one, so I will continue writing main. Since we need to know if the array is ordered or not, I will also make that non-existent call at this time. This method will be returning a boolean, so make sure to store it. print(ordered); inOrder = checkOrder(ordered); Now remember that if an array is not ordered, the binary search will not work. So we should write an if-else statement that handles this. Also, adding an appropriate error message is always useful. if(inOrder)
{
}
else
System.out.println("This array is not in order, I cannot search it.");
Within the if statement, we need to have code for getting the user to make guesses. First we'll print a statement saying that the array is ordered. Then we'll start our while loop, where the condition will be dependent on our "done" boolean because there are a few conditions that might kick us out of the loop. So now we have: if(inOrder)
{
System.out.println("This array is ordered.");
while(!done)
{
}
}
else
System.out.println("This array is not in order, I cannot search it.");
Within the while loop we will ask the user for input, store that input, incrememnt the number of guess the user has entered, and print out the guess. After that, we will conduct a search for the guess with another method call, which will be returning a boolean. Finally, as in any while loop, we need to check if we should stop the loop. The while loop should end if a guess was correct or if the maximum number of guess has been reached. The following code goes within the while loop. input = JOptionPane.showInputDialog("Enter the word you are looking for?",null);
count++;
System.out.println("Guess " +count +": " +input);
found = findString(input, ordered);
if(found || count == MAX_TRIES)
done = true;
The final part for our main method is to print out whether the user has met with success or not. We will use the "found" boolean for this; print a success message if "found" is true or a failure message if false. We also need to print out how many attempts it took. if(found)
{
System.out.println("By Jove, the array contains " +input +"!");
System.out.println("It took you " +count +" attempt(s) to get it.");
}
else
{
System.out.println("By Jove, it took you " +count +" tries and you still didn't get it?");
}
And that is it for the main method! We will now begin writing out the other methods, starting with the print method. Now remember, our print method is not going to return anything and it needs to be passed a String array to print, so the method header will be "public static void print(String [] array)". In the method, we will first print out a title, then each individual element in our array. A for loop is perfect for this job, since all we are doing is an array traversal. Then we print out an empty line at the end to make the final print out prettier. public static void print(String [] array)
{
System.out.print("Array: ");
for(int i = 0; i < array.length; i++)
System.out.print("\"" +array[i] +"\" ");
System.out.println();
}
Now for checking if an array is ordered. Since this method is returning a boolean, we need to mention this in the method header. Also, it will need to be passed an array to check, so the header will look like "public static boolean checkOrder(String [] array)". We'll first create our return variable and set it to false. We'll use a for loop for this because we're traversing an array again. Make sure that your loop stops one element sooner than the end because we are checking the current element against the next and we don't want any "out of bounds" errors. In the loop, we'll be checking each element to see if it is "less" than the next one. Since these are strings, we will need to use the "compareTo" method, and the result should come back as a negative number. If "compareTo" doesn't return a negative number, than the array is not in order and we need to set our return variable to false. Once the array is checked, we return our result. This gives us the folloing method. public static boolean checkOrder(String [] array)
{
boolean result = true;
for(int i = 0; i < array.length - 1; i++)
{
if(array[i].compareTo(array[i+1]) > 0)
result = false;
}
return result ;
}
Now for our binary search. This method will also be sent an array of Strings, a String to search for (the user's guess), and will be returning a boolean. The method header will be "public static boolean findString(String str, String [] array)". Now, unless your prof states otherwise, I highly suggest that you memorise how the binary search algorithm works. It's a very important algorithm, and even if it doesn't get asked for on an exam, it is still very useful to know for any future programming endeavours. The biggest thing to note in this algorithm is that Strings can't be compared by using < or > signs. So just use the "compareTo" method to make comparisons as you search. Remember that String's "compareTo" method will return a negative value if the String before the "period" comes after the String in the brackets, and will return a positive value if the Strings are the other way around. public static boolean findString(String str, String [] array)
{
boolean found = false;
int high;
int low;
int mid;
if(array != null)
{
high = array.length - 1;
low = 0;
while(!found && high >= low)
{
mid = (high + low) / 2;
if(array[mid].compareTo(str) < 0)
low = mid + 1;
else if(array[mid].compareTo(str) > 0)
high = mid - 1;
else
found = true;
}
}
return found;
}
And that's all there is to it! Whenever writing programs, always break up the problem into smaller pieces. It makes programming (and exam writing) so much less stressful. | ||
Code | ||
