3

我正在尝试从列表中查找大于某个值的值（在我的情况下已知）。

例子：

给定

list = [1, 2, 5, 10, 15];  //list is sorted

查找大于X(=7在这种情况下) 的值。

期望的结果 = 返回一个包含值的列表 =[10, 15]

我尝试使用java二进制搜索，比如

int index = Collections.binarySearch(list, X);

我的计划是找到 index (of X)，然后返回 index 之后的所有元素。

但是索引返回负数，我理解是因为7不在列表中。

还有其他方法吗？有人请建议。

4

5 回答 5

6

如果您的列表排序超过Collection#binarySearch将返回搜索键的索引，如果它包含在列表中；否则，（-（插入点）- 1）。您可以计算插入点的开始索引，如下所示：

     index= -(insertion_point) - 1
     -(insertion_point)= index+1
     insertion_point=-(index+1)

在获得List比的开始索引后，您可以应用subList方法来获得大于 X 的结果列表。

    Integer[] values = {1, 2, 5, 10, 15};
    List<Integer> list = new ArrayList<>(Arrays.asList(values));
    int X = 7;
    int index = Collections.binarySearch(list, X);

    int insertion_point = -(index+1); // As calculated above.

    List<Integer> res = list.subList(insertion_point, list.size());
    System.out.println(res);

输出：[10, 15]

于 2013-10-25T01:46:19.447 回答
2

从 Java 8 开始，您可以使用流。

import java.util.ArrayList;
import java.util.List;
import java.util.Arrays;
import java.util.stream.Collectors;

public class So1 {

   public static void main(String[] args) {
        List<Integer> list = Arrays.asList(1, 2, 5, 10, 15);
        List result = list.stream().filter(s -> s > 7).collect(Collectors.toList());
        System.out.println(result);
    }
}

对于这类数据计算，我强烈建议研究 Clojure，它可以编译为 Java。

例如，这是您编写它的方式：

(filter
    #(> % 7) 
    [1 2 5 10 15])
于 2013-10-25T02:07:55.847 回答
1

见Collections.binarySearch()：

回报：

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

即使元素不在列表中，该方法仍会返回有意义的内容，而这正是您想要的。如果返回值为r负，则插入点为-(r + 1)。当然，如果是正数，则r该元素包含在列表中。

于 2013-10-25T01:37:17.513 回答
0 
List<Integer> list;
List<Intger> out;

int v = 7;
for int i : list
    if i > v
        out.add(i)

如果这是一个小列表，蛮力方法将起作用。

您也可以使用 List 可用的一些方法，例如 subList -> List API

for int i; i < list.size() ; i++
    if list.get(i) > 7
         return list.subList(i,list.size())
return new List<Integer>() // return empty list
于 2013-10-25T01:45:54.340 回答
0

这样做的一个回合可能是使用传统的上、下和中点引用来实现你自己的二分搜索算法。通常，当在下面的方法中下端大于上端时，这意味着您要查找的数字不在列表中，但是在您的情况下，您可以将其用作列表中剩余项目的索引值的参考。

public int find(int searchKey){
    int lowerBound = 0;
    int upperBound = nElems-1;
    int check;

    while(true){
       check = (lowerBound + upperBound ) / 2;
       if(myArray[check]==searchKey){
           return check; // found it
        }else if(lowerBound > upperBound){
              //lowerbound is now the first index of the remaining values in the list.
              // I think. You might want to test it...

        }else{ // divide range
              if(myArray[check] < searchKey){
                 lowerBound = check + 1; // it's in upper half
              }else{
                   upperBound = check - 1; // it's in lower half
           }
        } // end else divide range
      } // end while
   } //
于 2013-10-25T01:53:29.050 回答