I'm writing a program to search for a string and tell me were it was found.
import java.io.*;
public class BinarySearchTest
{
public static void main(String [] args) throws IOException
{
int result;
String searchValue;
String input;
// An array of numbers to search.
String[] numbers = {"Jake", "Jerry", "Bill", "Lousie", "Goku", "Ivan", "John", "sarah", "kim"};
// Create the consol开发者_开发技巧e input objects.
InputStreamReader reader =
new InputStreamReader(System.in);
BufferedReader keyboard =
new BufferedReader(reader);
// First we must sort the array in ascending order.
IntQuickSorter.quickSort(numbers);
do
{
// Get a value to search for.
System.out.print("Enter a value to search for: ");
input = keyboard.readLine();
searchValue = input;
// Search for the value
result = IntBinarySearcher.i;
// Display the results.
if (result == -1)
System.out.println(searchValue + " was not found.");
else
{
System.out.println(searchValue + " was found at " +
"element " + result);
}
// Does the user want to search again?
System.out.print("Do you want to search again? (Y or N): ");
input = keyboard.readLine();
} while (input.charAt(0) == 'y' || input.charAt(0) == 'Y');
}
}
public class IntBinarySearcher
{
static int i;
public static int search(String[] numbers, String value)
{
int first; // First array element
int last; // Last array element
int middle; // Mid point of search
int position; // Position of search value
boolean found; // Flag
// Set the initial values.
first = 0;
last = numbers.length - 1;
position = -1;
found = false;
setI(Integer.parseInt(value));
// Search for the value.
while (!found && first <= last)
{
// Calculate mid point
middle = (first + last) / 2;
// If value is found at midpoint...
if (numbers[middle].equals(value))
{
found = true;
position = middle;
}
// else if value is in lower half...
// need tell is value is less then the integer?, with out using equality regulators
else if (value.compareTo(numbers[middle]) < 0)
last = middle - 1;
// else if value is in upper half....
else
first = middle + 1;
}
// Return the position of the item, or -1
// if it was not found.
return position;
}
public static void setI(int i)
{
IntBinarySearcher.i = i;
}
public static int getI()
{
return i;
}
}
public class IntQuickSorter
{
public static void quickSort(String[] numbers)
{
doQuickSort(numbers, 0, numbers.length - 1);
}
private static void doQuickSort(String[] numbers, int start, int end)
{
int pivotPoint;
if (start < end)
{
// Get the pivot point.
pivotPoint = partition(numbers, start, end);
// Sort the first sub list.
doQuickSort(numbers, start, pivotPoint - 1);
// Sort the second sub list.
doQuickSort(numbers, pivotPoint + 1, end);
}
}
private static int partition(String[] numbers, int start, int end)
{
String pivotValue; // To hold the pivot value
int endOfLeftList; // Last element in the left sub list.
int mid; // To hold the mid-point subscript
// Find the subscript of the middle element.
// This will be our pivot value.
mid = (start + end) / 2;
// Swap the middle element with the first element.
// This moves the pivot value to the start of
// the list.
swap(numbers, start, mid);
// Save the pivot value for comparisons.
pivotValue = numbers[start];
// For now, the end of the left sub list is
// the first element.
endOfLeftList = start;
// Scan the entire list and move any values that
// are less than the pivot value to the left
// sub list.
for (int scan = start + 1; scan <= end; scan++)
{
if (pivotValue.compareTo(numbers[scan])< 0) // pivotValue.compareTo(numbers[scan])< 0)
{
endOfLeftList++;
swap(numbers, endOfLeftList, scan);
}
}
// Move the pivot value to end of the
// left sub list.
swap(numbers, start, endOfLeftList);
// Return the subscript of the pivot value.
return endOfLeftList;
}
/**
The swap method swaps the contents of two elements
in an int array.
@param The array containing the two elements.
@param a The subscript of the first element.
@param b The subscript of the second element.
*/
private static void swap(String[] numbers, int a, int b)
{
String temp;
temp = numbers[a];
numbers[a] = numbers[b];
numbers[b] = temp;
}
}
There's something missing:
searchValue = input;
//IntBinarySearcher.search(numbers, searchValue); here?
// Search for the value
result = IntBinarySearcher.i;
Edit:
This won't work either since IntBinarySearcher.i
is never "correctly" set (see Edit2) :).
Better:
result = IntBinarySearcher.search(numbers, searchValue);
Edit 2:
Oh, and this would throw a NumberFormatException for value="Bill": setI(Integer.parseInt(value));
You don't appear to be performing the search. You need the line:
IntBinarySearcher.search(numbers, searchValue);
before the line:
result = IntBinarySearcher.i;
You don't call IntQuickSorter.search()
anywhere. Call it after
searchValue = input;
I don't see in your code where you're making a call to IntBinarySearcher.search. Without that i won't be set to anything, right?
精彩评论