當列表中不存在X時，從列表中找到大於X的列表

Question

我試圖從列表中查找大於特定值（在我的情況中已知）中的值。

實施例：

鑑於

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

查找（在這種情況下=7）值大於X。

期望的結果=返回與值的列表= [10, 15]

我試圖用java二進制搜索，像

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

我的計劃是尋找（的X）索引，然後返回所有之後的元素指數。

但索引返回否定，我明白，因爲7不在列表中。

有沒有其他辦法？有人請提出建議。

Answer 1

見Collections.binarySearch()：

返回：

搜索鍵的索引，如果它包含在列表中;否則，(-(insertion point) - 1）。插入點被定義爲鍵將被插入列表中的點：第一個元素的索引大於鍵，或者如果列表中的所有元素都小於指定的鍵，則爲list.size()。請注意，這保證返回值將大於等於0當且僅當找到密鑰。

即使元素不在列表中，該方法仍會返回有意義的東西，這正是您想要的。如果返回值r爲負值，則插入點爲-(r + 1)。當然，如果r是肯定的，那麼元素是包含在列表中。

Answer 2

List<Integer> list; 
List<Intger> out; 

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

蠻力的方法，如果這是一個小列表將工作。

你可以使用一些可用的清單，以及這些方法，如子列表 - >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 

Answer 3

如果列表比Collection#binarySearch排序將返回搜索鍵的索引，如果它包含在列表中;否則，（ - （插入點） - 1）。你可以計算出開始insertion_point的指數象下面這樣：得到的List的開始指數

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

後比你可以申請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]

Answer 4

A輪這樣做也可能是採用傳統的上，下和中點參考實現自己的二進制搜索算法的方式。通常，當下方的結果大於下方法中的上方時，這意味着您尋找的數字不在列表中，但是您可以將它用作對列表中其餘項目的索引值的引用。

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 
    } // 

Answer 5

自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); 
    } 
} 

對於那些類型的數據計算，我非常推薦查看編譯爲Java的Clojure。

例如，這是你會怎麼寫呢：

(filter 
    #(> % 7) 
    [1 2 5 10 15])