3

リストから特定の値（私の場合は既知）より大きい値を見つけようとしています。

例：

与えられた

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

より大きい値を検索しますX(=7この場合)。

望ましい結果 = 値のリストを返す =[10, 15]

次のように、Javaバイナリ検索を使用してみました

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

私の計画は、インデックス (のX) を見つけて、インデックスの後のすべての要素を返すことでした。

しかし、インデックスは負の値を返し7ます。これは、リストにないためです。

他の方法はありますか？誰か提案してください。

4

5 に答える 5

6

リストがCollection#binarySearchよりもソートされている場合、リストに含まれている場合、検索キーのインデックスが返されます。それ以外の場合は (-(挿入ポイント) - 1)。以下のように、insertion_point の開始インデックスを計算できます。

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

開始インデックスを取得した後、subListメソッドを適用して X より大きい結果のリストを取得Listできます。

    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 に答える
1

参照Collections.binarySearch():

戻り値：

リストに含まれている場合は、検索キーのインデックス。それ以外の場合は(-(insertion point)- 1)。挿入ポイントは、キーがリストに挿入されるポイントとして定義されます: キーより大きい最初の要素のインデックス、またはlist.size()リスト内のすべての要素が指定されたキーより小さい場合。これにより、キーが見つかった場合にのみ、戻り値が >= 0 になることが保証されることに注意してください。

要素がリストにない場合でも、メソッドは意味のあるものを返します。これはまさにあなたが望むものです。戻り値rが負の場合、挿入ポイントは-(r + 1)です。もちろん、rが正の場合、その要素はリストに含まれています。

于 2013-10-25T01:37:17.513 に答える
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 に答える
0 
List<Integer> list;
List<Intger> out;

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

これが小さなリストである場合、力ずくの方法が機能します。

subList -> List APIなど、List で使用できるメソッドの一部も使用できます。

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 に答える