Двоичный поиск сохраняет значение false, когда возвращаемое значение должно быть истинным

Question

Я использую NetBeans для программирования своего рода базы данных библиотек с номерами ссылок, чтобы найти книги. Я использую как линейные, так и двоичные запросы, чтобы определить, находится ли ссылочный номер в библиотеке, но двоичный поиск продолжает возвращать false, когда он должен быть истинным. Это то, что мой общий код выглядит как:

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); 
    } 

} 

} 

частей программы у меня возникли проблемы, с которыми эта часть:

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); 
    } 

} 

Я просто не понимаю, почему Двоичное возвращает ложь, когда он должен быть правдой. Даже линейный поиск возвращает true, когда это правда.

Answer 1

Я вижу, что вы используете тот же массив как для линейного поиска, так и для двоичного поиска.
Вы забыли отсортировать массив раньше?

Что делает бинарный поиск возможным, так это то, что данный массив сортируется - значения только идут в одну сторону (в основном увеличиваются).
Я не вижу никакой сортировки в вашем коде - самым важным условием для работы бинарного поиска является отсортированный массив. Если вы думаете об этом, то произойдет следующее: Массив «разрезается» на 2 части (без всякой информации, которая определяет каждую часть, в отличие от отсортированного массива, где одна часть больше средней, а другая меньше *), каждый раз, когда заданное значение и найденное значение не равны.
Поскольку массив не отсортирован, вероятность получения правильного значения довольно мала, поиск не имеет возможности найти нужное значение на основе значения, которое он «указывает» на
Ваш код сработал бы, если бы желаемое значение было посередине, или если «маршрут», который он принимает, каким-то образом приведет к нему (очень маловероятно, что это произойдет часто).

* может быть одинаковым. просто давая идею.