使用二进制搜索添加到一个ArrayList为了 [英] Using Binary Search to add to an ArrayList in order

问题描述

大家好，希望你能帮助我在这里，

Hello everyone hoping you can help me here,

我的问题是，我需要能够使用二进制搜索通过一个ArrayList来搜索并找到这样的清单是为了正确的地方加入一个对象。因为这是一门功课我不能使用集合排序。我已经正确实施，告诉如果列表包含你要搜索的项目的布尔方法。这code是在这里：

My problem is that I need to be able to search through an ArrayList using binary search and find where the correct place to add an object so that the list stays in order. I cannot use the collections sort as this is a homework. I have correctly implemented a boolean method that tells if the list contains an item you want to search for. That code is here:

    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）应该去。任何帮助是极大的AP preciated，谢谢！

What I need to do is use this method to see if the number already exists in the list and if that returns false then I need to be able to use another binary search to figure out where in the list the number (val) should go. Any help is greatly appreciated, thank you!!!

贾斯汀

推荐答案

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

Well instead of returning true or false, you can return the last index in your search. So if the value isn't in the List, then return the last index you visited, and see if the value is less than or larger than the current value at that index, and add the new value accordingly.

这篇关于使用二进制搜索添加到一个ArrayList为了的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！