Java集合binarySearch无法正常工作

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了Java集合binarySearch无法正常工作，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2504字，纯文字阅读大概需要4分钟。

内容图文

我只是想尝试使用原生Java二进制搜索,希望它总能找到第一次出现.但它并不总是第一次出现,我在这里做错了什么？

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不是没有gaurante那！任何人都可以举例说明如何找到给定元素的第一次出现和最后一次出现(比如User(10,null)？

非常感谢.

解决方法:

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).

内容总结

以上是互联网集市为您收集整理的Java集合binarySearch无法正常工作全部内容，希望文章能够帮你解决Java集合binarySearch无法正常工作所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端