0

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

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

谢谢你的帮助。

4

3 回答 3

2

计算median有问题：

median=(last-first)/2;

你应该这样做：

median=(last+first)/2;

在您拥有的当前代码中，当您在 range 中搜索时[10..16]，您的代码将尝试将目标与 的中位数进行比较list.get(3)。

可能还有另一个错误，但现在我将把这个留给你。提示： try [0, 1]，它应该暴露代码中的错误。

于 2013-04-29T14:22:47.080 回答
0

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

于 2013-04-29T14:40:11.007 回答
0

您可以直接使用 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 时添加冗余代码。

于 2015-02-02T12:49:26.253 回答