Java集合binarySearch无法正常工作 [英] Java collection binarySearch not working properly

问题描述

我只是想使用本机Java二进制搜索希望它总是可以找到第一次出现。但是它不总是返回第一次出现，我在这里做错了什么？

I am just trying to use native Java binarySearch hoping it can always find the first occurrence. But it's not always return the first occurrence, what have I done wrong here ?

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）？

Now it seems it's the API does not not gaurante that ! Can anyone give me working example of how to find the 1st occurrence and last occurrence for a given element (say User(10,null)?

p>

推荐答案

Java不会保证在等待的元素中返回的元素。等于范围，你需要走下列表找到与你正在寻找的第一个元素，如下：

Java does not make a guarantee as to which element among the equal ones it is going to return. When you have multiple elements in an equal range, you need to walk the list down to find the first element that's equal to what you are looking for, like this:

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

您可以将此逻辑封装在静态函数中，以避免每次都写入显式循环。

You can wrap this logic in a static function to avoid writing an explicit loop each time.

这篇关于Java集合binarySearch无法正常工作的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！