为什么binarySearch给我错误的索引？

我按自然顺序排列点的数组（使用自定义Point类），并保存对点的引用。然后使用比较器再次对其进行排序，然后使用binarySearch找到相同的点（确定指定当前顺序）。这是在一个循环的上下文中完成的，binarySearch每隔一次迭代就给我一个不正确的索引。为什么？为什么binarySearch给我错误的索引？

import java.util.Arrays; 

public class TestSearch { 

    public static void main(String[] args) { 

     Point[] pts = new Point[6]; 

     pts[0] = new Point(19000, 10000); 
     pts[1] = new Point(18000, 10000); 
     pts[2] = new Point(32000, 10000); 
     pts[3] = new Point(21000, 10000); 
     pts[4] = new Point(1234, 5678); 
     pts[5] = new Point(14000, 10000); 

     Arrays.sort(pts); 
     for (int i = 0; i < pts.length-2; i++) { 

      Point firstP = pts[i];  

      // Get a point from the array 
      Point secondP = pts[i+1]; 
      System.out.println("The point I saved: " + secondP.toString()); 

      // Find that same point and return it 
      // Why is this sometimes a different point? 
      Arrays.sort(pts, firstP.SLOPE_ORDER); 
      int secondI = Arrays.binarySearch(pts, secondP, firstP.SLOPE_ORDER); 
      System.out.println("The found point: " + pts[secondI].toString()); 
      System.out.println("-----"); 

      Arrays.sort(pts); 
     } 
    } 
}

这里是前两次迭代的输出。为什么它有时会返回与我搜索的不同点？

 
The point I saved: (14000, 10000) 
The found point: (14000, 10000) 
----- 
The point I saved: (18000, 10000) 
The found point: (19000, 10000) 
-----

继承人的定制点类，如果有帮助。

import java.util.Comparator; 

public class Point implements Comparable<Point> { 

    // compare points by slope 
    public final Comparator<Point> SLOPE_ORDER = new BySlope(); 

    private final int x; // x coordinate 
    private final int y; // y coordinate 

    // create the point (x, y) 
    public Point(int x, int y) { 
     this.x = x; 
     this.y = y; 
    } 

    // slope between invoking point and end point 
    public double slopeTo(Point end) { 
     if (end == null) 
      throw new java.lang.NullPointerException("Point object is null"); 
     if (this.equals(end)) 
      return Double.NEGATIVE_INFINITY; 
     if (end.x - this.x == 0) 
      return Double.POSITIVE_INFINITY; 
     return (double) (end.y - this.y)/(double) (end.x - this.x); 
    } 

    // is invoking point lexicographically smaller than second one? 
    // comparing y-coordinates and breaking ties by x-coordinates 
    public int compareTo(Point second) { 
     if (this.y < second.y) 
      return -1; 
     if (this.y == second.y && this.x < second.x) 
      return -1; 
     if (this.y > second.y) 
      return 1; 
     if (this.y == second.y && this.x > second.x) 
      return 1; 
     return 0; 
    } 

    // return string representation of this point 
    public String toString() { 
     return "(" + x + ", " + y + ")"; 
    } 

    private class BySlope implements Comparator<Point> { 

     @Override 
     public int compare(Point q1, Point q2) { 
      if (q1 == null || q2 == null) 
       throw new java.lang.NullPointerException("Point object" 
         + "is null"); 
      if (Point.this.slopeTo(q1) < Point.this.slopeTo(q2)) 
       return -1; 
      if (Point.this.slopeTo(q1) > Point.this.slopeTo(q2)) 
       return 1; 
      return 0; 
     } 

    } 
}

来源

2014-09-27 crayk

@ user2864740 - 但是我没有确保它们使用Arrays.sort（pts，firstP.SLOPE_ORDER）正确排序吗？ – crayk 2014-09-27 22:18:26

你的代码中有什么命中我的是你正在使用'Point'比较器来获得'secondP'并获得'pts [secondI]'你正在使用'BySlope'比较器。 – user902383 2014-09-27 22:34:14

我不明白你想用两种不同的比较类型来完成什么 - 你能给出一个你期望的结果的例子吗？ – wrschneider 2014-09-28 01:00:30

让我们稍微去掉它。显然，第一个Arrays.sort调用是无关的问题：binarySearch失败，并且这只是调用之后数组已被排序wrt。 “斜坡顺序”。

显然，问题出在您的Comparator。 Comparator本身没有任何问题，因为它似乎满足ComparatorJavadoc中确立的合同。但是，它与equals不一致：可能有点a,b，其中compare(a, b) == 0，但a.equals(b) == false。但是，由于二分查找只能“查看”比较器建立的顺序，因此无法区分a和b，因此它可能会返回“看起来像”其中任何一个的第一个元素。

你的问题是，你通过你的比较定义这些点a和b等同，但仍然预计二进制搜索和区分它们返回一个点，不仅是等效的，但等于到你提供的一个。尝试输出firstP.slopeTo(secondPt)和firstP.slopeTo(pts[secondI]) - 这些值是否相等？

最后，一个解决方案是通过默认点的自然顺序来打断订单中的关系。也就是说，将BySlope.compare中的return 0;替换为return q1.compareTo(q2)。

来源

2014-09-28 23:49:05 misberner

为什么binarySearch给我错误的索引？

回答

相关问题