搜索排序列表<长>最近和小于

Question

考虑一些long叫做X和排序的List<Long>.什么是找到索引或值的最有效的算法List<Long>是(i)小于X,和(ii)最接近X数字线(假设条件(i)已被饱和)？

例如,这可能是一个问题设置:

long X = 500;
List<Long> foo = new Arraylist<Long>();
foo.add(450L);
foo.add(451L);    
foo.add(499L);
foo.add(501L);
foo.add(550L);

Collections.sort(foo); // It's always sorted.

我希望算法返回499或返回与之关联的索引499(在本例中i=2).

Answer 1

鉴于列表中的值是唯一的,我建议您使用a Set,更具体地说是a TreeSet,因为您无论如何都要对列表进行排序.您可以使用NavigableSet#floor(E)完全符合您要求的方法.

返回此set中小于或等于给定元素的最大元素,或者null如果没有这样的元素.

所以,代码看起来像:

long X = 500;
NavigableSet<Long> foo = new TreeSet<Long>();

foo.add(450L);
foo.add(451L);    
foo.add(499L);
foo.add(501L);
foo.add(550L);

System.out.println(foo.floor(X));   // 499

该方法也适用于用户定义的对象.只需在实例化时将a传递Comparator<YourClass>给TreeSet构造函数.

Answer 2

/*找到列表中最近的数字*@param整数列表*@param num找到最接近的数字*@return最接近的数字**/

public static int findClosestNumber(List list, int num) {
    if (list.size() > 0) { // Check list does not empty
        int smaller =
            (Integer)Collections.min(list); // get min number from the list
        int larger =
            (Integer)Collections.max(list); // get max number from the list

        for (int i = 0; i < list.size(); i++) { //Traverse list
            if (num == (Integer)list.get(i))   //if find the passed number in the list
                return num;                     //than return num
            if (num > (Integer)list.get(i) && smaller < (Integer)list.get(i)) // find nearest smaller
                smaller = (Integer)list.get(i);
            if (num < (Integer)list.get(i) && larger > (Integer)list.get(i)) // find nearest larger
                larger = (Integer)list.get(i);
        }
        return (num - smaller < larger - num ? smaller : larger); // return closest number
    }
return 0;
}

}

Answer 3

您可以使用java Collections.binarySearch,因为您的列表已排序.

在规范中,二进制搜索返回:

搜索关键字的索引,如果它包含在列表中; 否则,( - (插入点) - 1).插入点定义为键将插入列表的点:第一个元素的索引大于键,或者list.size(),如果列表中的所有元素都小于指定的键.请注意,当且仅当找到密钥时,这可以保证返回值> = 0.

首先,如果你进行二元搜索并且元素在列表中,你将获得一个正值(元素的索引),并且可以返回(或者如果你仍然想要一个更少的元素,你可以向后走从那里直到你找到一个).

否则,如果搜索不在列表中的内容,则可以从返回值向后工作到所需的索引.如果在示例列表中搜索500,则算法将返回(-3 - 1)= -4.因此,您可以添加1以返回插入点(-3),然后乘以-1并减去1以获得索引BEFORE第一个元素GREATER而不是您搜索的元素,这将是一个索引如果列表中的所有元素都大于您搜索的元素,则符合您的2个条件或-1.

在树集上使用二进制搜索的优点是它可能具有更少的开销.