5

ネイティブJavabinarySearchを使用しようとしていますが、常に最初の出現を見つけることができることを望んでいます。しかし、それは常に最初の発生を返すわけではありません、私はここで何を間違えましたか？

import java.util.*;

class BinarySearchWithComparator
{
  public static void main(String[] args)
  {
    // Please scroll down to see 'User' class implementation.
    List<User> l = new ArrayList<User>();
    l.add(new User(10, "A"));
    l.add(new User(10, "A"));
    l.add(new User(10, "A"));

    l.add(new User(20, "B"));
    l.add(new User(20, "B"));
    l.add(new User(20, "B"));
    l.add(new User(20, "B"));
    l.add(new User(20, "B"));
    l.add(new User(20, "B"));
    l.add(new User(20, "B"));


    l.add(new User(30, "C"));
    l.add(new User(30, "C"));
    l.add(new User(30, "C"));
    l.add(new User(30, "C"));

    Comparator<User> c = new Comparator<User>() {
      public int compare(User u1, User u2) {
        return u1.getId().compareTo(u2.getId());
      }
    };

    // Must pass in an object of type 'User' as the key.
    // The key is an 'User' with the 'id' which is been searched for.
    // The 'name' field is not used in the comparison for the binary search,
    // so it can be a dummy value -- here it is omitted with a null.
    //
    // Also note that the List must be sorted before running binarySearch,
    // in this case, the list is already sorted.
    Collections.sort(l,c);

    int index = Collections.binarySearch(l, new User(10, null), c);
    System.out.println(index);

    index = Collections.binarySearch(l, new User(20, null), c);
    System.out.println(index);

    index = Collections.binarySearch(l, new User(30, null), c);
    System.out.println(index);

    index = Collections.binarySearch(l, new User(42, null), c);
    System.out.println(index);
  }
}

class User {
  private int id;
  private String name;

  public User(int id, String name) {
    this.id = id;
    this.name = name;
  }

  public Integer getId() {
    return Integer.valueOf(id);
  }
}

========

Result:
2 //not 0 ?
6 //not 3?
10 //ok
-15  ok

Why first 10 is not index 0 ?
Why first 20 is not index 3 ?
OK , 30 first occurrence is index 10

======================================

アップデート

今では、APIはそれを保証していないようです！特定の要素（たとえばUser（10、null））の最初の出現と最後の出現を見つける方法の実用的な例を誰かに教えてもらえますか？

どうもありがとう。

4

4 に答える 4

10

Javaは、等しい要素の中でどの要素を返すかについて保証しません。同じ範囲に複数の要素がある場合は、リストを下に移動して、次のように、探しているものと等しい最初の要素を見つける必要があります。

User lookFor = new User(30, null);
index = Collections.binarySearch(l, lookFor, c);
while (index > 0 && c.compare(lookFor, l[index-1]) == 0) {
    index--;
}
// At this point the index is at the first element of the equal range

このロジックを静的関数でラップして、毎回明示的なループを記述しないようにすることができます。

コレクションがランダムアクセスの場合、これにより最悪の場合のパフォーマンス（同一の要素が多数ある場合）がO（lg（n））からO（n）に低下することに注意してください。

于 2013-03-25T01:23:31.227 に答える
5

ただし、リストにID10の要素が複数あります。したがって、binarySearchは間違っていません

binarySearchのJavaマニュアルには、次のように書かれています。

二分探索アルゴリズムを使用して、指定されたリストで指定されたオブジェクトを検索します。この呼び出しを行う前に、リストをその要素の自然な順序（sort（List）メソッドなど）に従って昇順でソートする必要があります。ソートされていない場合、結果は未定義です。リストに指定されたオブジェクトと等しい複数の要素が含まれている場合、どれが見つかるかは保証されません。

http://docs.oracle.com/javase/6/docs/api/java/util/Collections.html#binarySearch(java.util.List、T）

于 2013-03-25T01:19:33.027 に答える
1

Array.binarySearch（）のjavadocから：

Searches a range of the specified array of bytes for the specified value using the
binary search algorithm. The range must be sorted (as by the sort(byte[], int, int) 
method) prior to making this call. If it is not sorted, the results are undefined. 
If the range contains multiple elements with the specified value, there is no 
guarantee which one will be found.
于 2013-03-25T01:21:02.110 に答える
1

リスト内のアイテムの多くは、並べ替えの目的で同じです。2つのアイテムのIDが同じである場合、並べ替えの観点からは、どちらを使用してもかまいません。Collections.binarySearchは、一致するものが見つかるまでリストを半分に分割します。一致するものが見つかると、前のアイテムをチェックしてそれが一致するかどうかを確認するのではなく、インデックスを返すだけです。

アイテムにIDがある場合は、IDだけでなくソートするより堅牢なcompareTo実装を検討してください。

于 2013-03-25T01:21:18.330 に答える