在Android中搜索整数ArrayList的最佳方法

Question

我有一个整数的ArrayList.

例如,假设一个具有整数0,4,7,10的ArrayList

我现在想比较任何给定的整数,看看它在ArrayList上的位置.

所以例如,如果我的整数是3,它应该在0和4之间,所以结果将是1.如果我的整数是9,它将在7和10之间,所以我的结果将是3.

显然我可以循环遍历整个ArrayList,如下所示:

    int indexOfItem = 0;
    if (mylist.size()>0)
        while (indexOfItem<mylist.size() && integerImSearching>mylist.get(itemsToSkip)) {
            indexOfItem++;          
        }

我可以从这个方法中获取我的项目的索引.但是这很好,如果ArrayList很小,我担心如果列表相当大,它不是最佳方式.有没有更好的方法来实现这一目标？

Answer 1

由于您的ArrayList内容已排序,您应该使用它Collections.binarySearch来查找您的项目.这将使每次搜索O(log n)而不是O(n).

此函数返回项目的索引(如果找到),或者返回其插入位置的补码.因此,为了您的目的,您可以这样做:

int lowerBound(List<Integer> list, int item) {
    int result = Collections.binarySearch(list, item);
    return result >= 0 ? result : ~result;
}