java - 使用二进制搜索按顺序添加到 ArrayList

Question

大家好，希望你能帮到我，

我的问题是我需要能够使用二进制搜索来搜索 ArrayList 并找到添加对象的正确位置，以便列表保持有序。我不能使用集合排序，因为这是一项作业。我已经正确地实现了一个 boolean 方法，该方法告诉列表是否包含您要搜索的项目。该代码在这里:

    public static boolean search(ArrayList a, int start, int end, int val){
    int middle = (start + end)/2;
    if(start == end){
        if(a.get(middle) == val){
            return true;
        }
        else{
            return false;
        }
    }
    else if(val < a.get(middle)){
        return search(a, start, middle - 1, val);
    }
    else{
        return search(a, middle + 1, end, val); 
    }
}

我需要做的是使用此方法查看数字是否已存在于列表中，如果返回 false，那么我需要能够使用另一个二进制搜索来找出数字在列表中的位置 (val)应该去。非常感谢任何帮助，谢谢!!!

贾斯汀

Answer 1

好吧，您可以返回搜索中的最后一个索引，而不是返回 true 或 false。因此，如果该值不在列表中，则返回您访问的最后一个索引，并查看该值是小于还是大于该索引处的当前值，并相应地添加新值。