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.

zw324 · Accepted Answer · 2013-04-29 14:22:47Z

2

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.

answered Apr 29, 2013 at 14:22

zw324

27.2k16 gold badges88 silver badges119 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

Joop Eggen Over a year ago

And first = median + 1; instead of just median. Further while (first < last).

zw324 Over a year ago

@JoopEggen yeah, I didn't give OP the answer, but added a hint.

zw324 Over a year ago

@UmNyobe um, any reason for using that? Could it work without set fst = med + 1?

Daniel Fischer Over a year ago

@ZiyaoWei If the list is large enough, first + last can overflow. (last - first)/2 + first, or, as UmNyobe wrote, (first - last)/2 + last cannot overflow (for 0 <= first <= last).

zw324 Over a year ago

@DanielFischer Ah I see. Thanks! (Although before overflowing, the memory probably ran out first under most circumstances, and we can always use long8) )

|

Zim-Zam O'Pootertoot · Accepted Answer · 2013-04-29 14:40:11Z

0

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.

answered Apr 29, 2013 at 14:40

Zim-Zam O'Pootertoot

18.2k4 gold badges45 silver badges71 bronze badges

5 Comments

marek Over a year ago

Ok, I used median=((last-first)/2)+first in my code. I also used if(element>l){last = median-1; ...}, then I added else if(element==l){break;} and else if(!list.contains(l)){break;} and used while(first<last); instead of while(element!=l); Now it seems it works. What do you think?

Zim-Zam O'Pootertoot Over a year ago

Take out !list.contains(1) - this will do a linear search of the entire list. Instead, replace it with else break; to exit the loop when you've found the element.

marek Over a year ago

Done. Is the rest of the code right? Does binary search work now?

Zim-Zam O'Pootertoot Over a year ago

I think your code should return a boolean to indicate whether the element was found. Other than that it looks like it's ready for testing.

marek Over a year ago

When I type any number in the range of the list, program will finish after a few miliseconds - in addition I used System.currentTimeMillis() method to count how much time has been taken between choosing the number and finding it.

codechefvaibhavkashyap · Accepted Answer · 2015-02-02 12:49:26Z

0

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.

answered Feb 2, 2015 at 12:49

codechefvaibhavkashyap

1,01520 silver badges33 bronze badges

Collectives™ on Stack Overflow

Binary search algorithm does not work properly - Java

3 Answers 3

7 Comments

5 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

7 Comments

5 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related