二进制搜索算法不能正常工作- Java

Question

我想让我自己的二进制搜索算法来搜索1 000 000个元素的ArrayList。我决定用do-while循环来搜索。我知道我可以使用while()循环。但是当我运行它时，要花很多时间才能找到这个数字。我猜设置数组列表的第一个和最后一个元素的值是错误的。我的代码是

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

谢谢你的帮助

Answer 1

median计算有问题:

median=(last-first)/2;

你应该这样做:

median=(last+first)/2;

在你现有的代码中，当你在[10..16]范围内搜索时，你的代码将尝试将目标与list.get(3)的中位数进行比较。

可能还有另一个bug，但是现在我就把这个留给你。提示:尝试[0, 1]，它应该会暴露代码中的错误。

Answer 2

正如魏子尧回答的那样，你需要修正中位数。另外，您可能需要一个不同的循环退出条件——现在如果l不在列表中，您就会得到一个无限循环。此外，您的if-else需要是if-elseif-else -目前如果l == element，那么循环实际上会将其视为element > l并继续循环。

Answer 3

可以直接使用Collection类的二进制搜索方法呈现java。Util包:-

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

和

public class MyTransferObjectClass implements Comparator<MyTransferObjectClass>{
@Override
    public int compare(MyTransferObjectClass o1, MyTransferObjectClass o2) {
                //your logic for comparison
    }
}

当你可以使用可用的api时，为什么要添加多余的代码