Binary search algorithm does not work properly - Java

Question

I want to make my own binary search algorithm to search ArrayList of 1 000 000 elements. I decided to do the search with do-while loop. I am aware I could use while() loop. But when I run it, it takes much time to find the number. I guess something is wrong with setting the value of first and last element of ArrayList. My code is

import java.util.*;

public class BinSearchAlg {
public static void main(String[]args){

    int first;
    int last;
    int median;//middle element of arraylist
    Long element;//element with median index
    Scanner scan = new Scanner(System.in);
    ArrayList<Long>list = new ArrayList();
    for(long l=0;l<1000000;l++){
        list.add(l);//list is sorted
    }
    first = 0;
    last = list.size();
    median = (last-first)/2;
    element = list.get(median);
    System.out.println("Choose the number: ");
    long l = scan.nextLong();
    do{
        if(element<l){
            first = median;
            median=(last-first)/2;
            element = list.get(median);
        }else{ //if(element>l){
            last = median;
        median = (last-first)/2;
        element = list.get(median);
        }
    }while(element!=l);
}
}

Thanks for you help.

Answer 1

The median calculation is problematic:

median=(last-first)/2;

You should rather do:

median=(last+first)/2;

In the current code you have, when you are searching in the range [10..16], your code will try to compare the goal with the median of list.get(3).

There could be another bug, but for now I'll leave you with this. Hint: try [0, 1], which should expose the bug in the code.

Answer 2

As Ziyao Wei answered, you'll need to fix the median. In addition, you'll probably need a different loop exit condition - right now you've got an infinite loop if l isn't in the list. Also, your if-else needs to be an if-elseif-else - at present if l == element then the loop will actually treat this as element > l and continue looping.

Answer 3

You can directly use Collection class's binary search method present java.util package :-

Collections.binarySearch(myList,key.get(i),new MyTransferObjectClass());

and

public class MyTransferObjectClass implements Comparator<MyTransferObjectClass>{

@Override
    public int compare(MyTransferObjectClass o1, MyTransferObjectClass o2) {
                //your logic for comparison
    }

}

why to add redundant code when you can use available APIs.