Бинарный поиск Java

Question

Я работаю над проектом, в котором он читает названия книг из файла.txt и помещает их в массив, затем массив преобразуется в массив. Пользователь вводит число, которое является ссылочным номером книги, затем выполняет линейное поиск и бинарный поиск, чтобы найти эту книгу. У меня просто проблемы с кодом для бинарного поиска, так как я почти не знаю, как это сделать, вот что у меня есть:

   private void FindItActionPerformed(java.awt.event.ActionEvent evt) {                                       
String input;

input = Input.getText();

for(int i=0; i<bookList.length; i++){
if (bookList[i].referenceNumber.equals(input)){
    Output1.setText("The Book is " + bookList[i].title);
}
}

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

int right = 0, left = bookList.length;
while(right<= left){
    int middle = (right + left)/2;
    if( bookList[middle].referenceNumber.equals(input)){
        Output2.setText("The book is " + bookList[middle].title);     
    }
}

}    

Вот класс и массивы

 public class Book{
String referenceNumber, title;

public Book(String _referenceNumber, String _title){
   referenceNumber = _referenceNumber;
   title = _title;
}
}

 ArrayList <Book> Books = new ArrayList <Book> ();
 Book [] bookList;

Спасибо за любую помощь, которую вы можете предложить. Это немного сложно для меня.

Answer 1

У меня были проблемы, когда я учился кодировать бинарный поиск, а также. Первое, что вы должны знать, это то, что вам не нужно выполнять бинарный поиск и линейный поиск, вам нужно только выполнить одно или другое. Также для выполнения бинарного поиска вам нужно отсортировать ваш массив ex int[] array = {1,2,3,4,5,6,7,8,9,10}; Что делает бинарный поиск, так это просматривает средний элемент массива и проверяет, больше или меньше элемент ключа. Если он меньше всего меньше, то средний элемент игнорируется (то же самое для большего - все, что больше, выбрасывается). Затем выбирается новый средний элемент и половина отбрасывается, и это делается до тех пор, пока ключ не будет найден. Ниже приведен код для сортировки массива int, вам нужно изменить его, чтобы он возвращал книги (строку? Или книгу классов, которую вы, возможно, написали)

public static boolean binarySearch(int[] array, int key){
    int partition = 0;
    int right = array.length - 1;
    boolean found = false;
    int left = 0;






    while(! found && left <= right){

        if(array[partition] == key){
            found = true;
        }


    if(array[partition] > key){//key less
        right = partition - 1;
        partition = (right + left) / 2;
    }

    if(array[partition] < key){//key greater
        left = partition + 1;
        partition = (left + right) / 2;


    }



    }
    return found;

}

Также здесь приведен код для сортировки массива целых. Это пузырьковая сортировка, поэтому она медленная. ^2

public int[] bubbleSort(int[] array){
    int temp;
    boolean keepGoing = true;

    while(keepGoing == true){
    keepGoing = false;
        for(int i=0; i < array.length - 1; i++){
        if(array[i] > array [i + 1]){ //if i < i + 1 means greatest to smallest if 
                                        // if i > i + 1 means smallest to greatest
            swap(array, i, i + 1);
            keepGoing = true;

        }
    }
    }


    return array;

    }

Код прост, придется изменить его, чтобы отсортировать книги, метод swap ниже

public int[] swap(int[] array, int i, int j){
    int temp = 0;
    temp = array[i];
    array[i] = array[j];
    array[j] = temp;
    return array;
}

Answer 2

Хорошая визуализация бинарного поиска на http://balance3e.com/Ch8/search.html Например, попробуйте ввести FL и посмотреть, как алгоритм ищет его шаг за шагом. Вы получите это быстро:)

Это работает как поиск слова в словаре... Вы ищете "кошку", например, поэтому вы открываете свой словарь пополам и видите слово "человек", это по лексикографии больше, чем "кошка", так что вы будете искать слева от "man" = в первой половине словаря...

Затем вы только повторяете этот процесс деления на более мелкие части, пока не найдете то, что искали.