搜索排序列表最近和小于
考虑一些long叫做X和一个有序的List 。 在List中找到索引或值的最有效算法是什么（i）小于X ，以及（ii）在数字行上最接近X （假设条件（i）已被饱和）？
例如，这可能是一个问题设置：
long X = 500; List foo = new Arraylist(); 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 ）。
鉴于列表中的值是唯一的，我建议您使用Set ，更具体地说是TreeSet ，因为您无论如何都要对列表进行排序。 您可以使用NavigableSet#floor(E)方法，它完全符合您的要求。
返回此set中小于或等于给定元素的最大元素，如果没有这样的元素，则返回
null。
所以，代码看起来像：
long X = 500; NavigableSet foo = new TreeSet (); foo.add(450L); foo.add(451L); foo.add(499L); foo.add(501L); foo.add(550L); System.out.println(foo.floor(X)); // 499
该方法也适用于用户定义的对象。 只需在实例化时将Comparator传递给TreeSet构造函数。
/ *找到列表中最近的数字* @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; }
}
您可以使用java的Collections.binarySearch ，因为您的列表已排序。
在规范中 ，二进制搜索返回：
搜索关键字的索引，如果它包含在列表中; 否则，（ – （插入点） – 1）。 插入点定义为键将插入列表的点：第一个元素的索引大于键，或者list.size（），如果列表中的所有元素都小于指定的键。 请注意，当且仅当找到密钥时，这才能保证返回值> = 0。
首先，如果你进行二元搜索并且元素在列表中，你将获得一个正值（元素的索引），并且可以返回（或者如果你仍然想要一个更少的元素，你可以向后走从那里直到你找到一个）。
否则，如果搜索不在列表中的内容，则可以从返回值向后返回所需的索引。 如果在示例列表中搜索500，则算法将返回（-3 – 1）= -4。 因此，您可以添加1以返回插入点（-3），然后乘以-1并减去1以获得索引BEFORE第一个元素GREATER而不是您搜索的元素，这将是一个索引如果列表中的所有元素都大于您搜索的元素，则符合您的2个条件或-1。
在树集上使用二进制搜索的优点是它可能具有更少的开销。