I am using NetBeans to program a sort of library database with reference numbers to find the books. I am using both Linear and Binary searches to determine if the reference number is in the library, but the binary search keeps returning false when it should be true. This is what my overall code looks like:
package u3a3_bookslist;
import java.util.*;
import java.io.*;
public class bookslist {
//Define the default variables to use in all other methods of the program
public static int index, numSearches;
public static void main(String[] args) {
//Define the ArrayList to store the values of 'BookList.txt'
ArrayList <String> books = new ArrayList <String>();
//Define the default values to use later in the code
BufferedReader br = null;
String referenceNumber;
//Use a try statement to analyze the entire 'BookList.txt' file and add
//each value on a new line into the arrayList 'books'
try {
br = new BufferedReader(new FileReader("BookList.txt"));
String word;
while ((word = br.readLine()) != null ){
books.add(word);
}
} catch (IOException e) {
e.printStackTrace();
} finally {
try {
br.close();
} catch (IOException ex) {
ex.printStackTrace();
}
}
//Create a new Array called 'bookList' to store and convert all the values
//from the 'books' arrayList
String [] bookList = new String[books.size()];
books.toArray(bookList);
//Create a scanner input to ask the user to enter a reference number
Scanner input = new Scanner(System.in);
System.out.println("Enter the reference number of a book to determine"
+ " if it is in the library or not: ");
//Set the variable 'referenceNumber' to whatever value that the user inputted
//into the Scanner
referenceNumber = input.next();
//Obtain the boolean result of either true or false from the Binary and
//Linear search methods
Boolean resultLinear = linearSearch(bookList, referenceNumber);
Boolean resultBinary = binarySearch(bookList, 0, bookList.length-1, referenceNumber);
//Analyze each element that is contained in the 'bookList' Array
for (int i = 0; i < bookList.length; i++) {
//Determine if the value of 'i' is equal to the 'referenceNumber'
//converted into an int format
if (i == Integer.parseInt(referenceNumber)) {
//Determine if the 'i' index of the 'bookList' Array is equal
//to the user inputted reference number
if (bookList[i].equals(referenceNumber)) {
//If the previous statement were true, the 'index' variable
//was set to equal to current value for 'i'
index = i;
}
}
}
//Determine the message to display to the user depending on if the reference
//number was found in the Array using a Linear Search
if (resultLinear == true) {
System.out.println("Linear Search: Reference Number " + referenceNumber +
" was found in the library. The book with that number is: " + bookList[index+1]);
} else {
System.out.println("Linear Search: Reference Number " + referenceNumber
+ " not in the library. No book with that number.");
}
//Determine the message to display to the user depending on if the reference
//number was found in the Array using a Binary search
if (resultBinary != false) {
System.out.println("Binary Search: Reference Number " + referenceNumber +
" was found in the library. The book with that number is: " + bookList[index+1]);
} else {
System.out.println("Binary Search: Reference Number " + referenceNumber
+ " not in the library. No book with that number.");
}
}
//Execute a linear search to determine if the user inputted reference number
//is contained in the bookList Array
static public Boolean linearSearch(String[] A, String B) {
for (int k = 0; k < A.length; k++) {
if (A[k].equals(B)) {
return true;
}
}
return false;
}
//Execute a binary search to determine if the user inputted reference number
//is contained in the bookList Array
public static Boolean binarySearch(String[] A, int left, int right, String V) {
int middle;
numSearches ++;
if (left > right) {
return false;
}
middle = (left + right)/2;
int compare = V.compareTo(A[middle]);
if (compare == 0) {
return true;
}
if (compare < 0) {
return binarySearch(A, left, middle-1, V);
} else {
return binarySearch(A, middle + 1, right, V);
}
}
}
The parts of the program I am having problems with are this part:
public static Boolean binarySearch(String[] A, int left, int right, String V) {
int middle;
numSearches ++;
if (left > right) {
return false;
}
middle = (left + right)/2;
int compare = V.compareTo(A[middle]);
if (compare == 0) {
return true;
}
if (compare < 0) {
return binarySearch(A, left, middle-1, V);
} else {
return binarySearch(A, middle + 1, right, V);
}
}
I just don't understand why the Binary Search returns false when it is supposed to be True. Even the Linear Search returns true when it is true.
I see that you are using the same array for both linear search and for binary search.
Did you forget to sort the array before?
What make the binary search possible is the fact that the given array is sorted - the values only go in one way (getting greater mostly).
I can't see any kind of sorting in your code - the most important condition for binary search to work is a sorted array. If you think about it, what happen is: The array is being "cut" into 2 parts (without anything that defines each part, unlike a sorted array where one part is greater than the middle and the other is smaller*), every time the given value and the found value are not equal.
Because the array is not sorted, the chance of getting the right value is quite small, the search has no way to find the value you want based on the value he is "pointing" at
Your code would have worked if the wished value was at the middle or if the "route" it takes would somehow lead to it (very unlikely to happen often).
*might as well be equal. just giving the idea.