Binary Search Java

Question

Im working on a project in which it reads book titles in from a .txt file and puts them into an arraylist, then the arraylist is converted to an array, The user enters a number which is the books reference number, then it does a linear search and a binary search to find that book. Im just having a trouble with the code for the binary search,as i have almost no idea how to do it, heres what I have:

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

Above is the code for the linear search, which works fine. Below is what i think i need for the binary search but again, i am not sure and cannot figure it out.

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

}    

Here is the class and the arrays

 public class Book{
String referenceNumber, title;

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

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

Thanks for any help you may be able to offer, This is a bit tricky for me.

Answer 1

I had problems when I was learning to code binary search aswell. The first thing you should know is that you do not have to do a binary search and a linear search, you only need to do one or the other. Also to do a binary search you need to sort your array ex int[] array = {1,2,3,4,5,6,7,8,9,10}; What a binary search does is it looks at the middle element in the array and tests to see if the element is greater or less than the key. If it is less everything less then the middle element is ignored (same for bigger just everything bigger is thrown away). Then a new middle element is selected and half is thrown away, and this is done until the key is found. Below is the code for sorting a int array, you would need to modify it to return books (string? or the class book you may have written)

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;

}

Also here is some code for sorting an array of ints. This is a bubble sort so it is slow On^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;

    }

The code is simple would have to modify it to sort your books the method swap is below

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

There is nice visualisation of binary search at http://balance3e.com/Ch8/search.html For example try to enter FL and watch the algorithm looking for it step by step. You will get it quickly :)

It works like looking up a word in a dictionary... You are looking for "cat" for example, so you open your dictionary in half and see word "man" this is lexicographicaly bigger than "cat", so you will be looking to the left from "man" = in first half of the dictionary...

Then you only repeat this process of dividing into smaller parts until you find what you were looking for.