使用二分搜索按顺序添加到 ArrayList [英] Using Binary Search to add to an ArrayList in order

问题描述

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

Hello everyone hoping you can help me here,

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

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)应该去.非常感谢任何帮助，谢谢！！！

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.因此，如果该值不在 List 中，则返回您访问的最后一个索引，并查看该值是否小于或大于该索引处的当前值，并相应地添加新值.

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屋！