Difference between revisions of "String Binary Search"
Line 17: | Line 17: | ||
</pre> | </pre> | ||
− | |SideSectionTitle= | + | |SideSectionTitle=Problem Solving and Programming Examples |
|SideSection= | |SideSection= | ||
[[Image:Wiki_bench01.jpg|center]] | [[Image:Wiki_bench01.jpg|center]] | ||
Line 27: | Line 27: | ||
<pre> | <pre> | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
</pre> | </pre> | ||
Line 44: | Line 37: | ||
<pre> | <pre> | ||
− | import javax.swing.*; | + | import javax.swing.*; |
public class StringBinarySearch | public class StringBinarySearch |
Revision as of 15:08, 8 April 2010
Back to the Program-A-Day homepage
ProblemYou are given an ordered array of Strings. Your program will do a few things. First, it must verify that the array is indeed ordered. This will be done in a separate method, and the mothod 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. Another method will then be required to conduct a binary search of 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 output, the program will first print the array. Then it will print the 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
| |
---|---|---|
SolutionWe shall first start by declaring our variables:
| ||
CodeSolutionCode goes here. Please DO NOT put your code in <pre> tags! |
import javax.swing.*; public class StringBinarySearch { public static void main(String [] args) { final int MAX_TRIES = 5; boolean done = false; boolean found = false; String input = ""; int count = 0; String [] notOrdered = {"the","cake","is","a","lie"}; String [] ordered = {"a","cake","is","lie","the"}; boolean bool = inOrder(ordered); if(bool) { while(!done) { input = JOptionPane.showInputDialog("Enter the word you are looking for?",null); count++; found = findString(input, ordered); if(found || count == MAX_TRIES) done = true; } } else System.out.println("This array is not in order, I cannot search it."); 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?"); } } public static boolean inOrder(String [] array) { boolean bool = true; for(int i = 0; i < array.length - 1; i++) { if(array[i].compareTo(array[i+1]) > 0) bool = false; } return bool; } private 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; } }