java - 对点间隔执行二进制搜索

Question

我将尽可能清楚地解释我的问题。 Point[] right 是一个有序的点数组，每个 Point 对象都是一对 Long x, y。

现在，这就是我的目标。给定一个 Point p 及其 p.y 坐标，我必须找到几个点 Point p1, p2 其中(根据 y 坐标) p 被包括在内，显然使用二分查找。这是我的迭代实现。

        /* Binary search for leftmost edge intersected by p */
        Point p1, p2;
        long px = p.x, py = p.y;
        long div = 2;
        long index = (left.length-1)/div;
        while(true) {
//          System.out.println("Left search-index:"+index+" Div: "+div);
            if(left[(int) index].y.compareTo(p.y) >= 0){
                if(left[(int) (index+1)].y.compareTo(p.y) <= 0){    
                    p1 = left[(int) index];
                    p2 = left[(int) (index + 1)];
//                  System.out.println("p1 "+p1.x+" "+p1.y+"; p2 "+p2.x+" "+p2.y);
                    break;
                }
                else {
                    if(index/div == 0)
                        index = index + 1;
                    else
                        index = index + index/div;
                }
            }
            else {
                if(index/div == 0)
                    index = index - 1;
                else index = index - index/div;
            }
            div = 2*div;
        }

现在，问题:

1. 这实际上是二分查找吗？
2. div 会溢出吗？我知道在运行时它会抛出异常，但我不知道是什么以及由谁抛出。 (这个问题发生在 SPOJ 提交上，我唯一的信息是 NZEC Runtime Error)。
3. 有提高性能的方法吗？我期待一个包含 5000-10000 个点的数组。

我尝试使用 75+ 条目数组，并且有执行的痕迹。 (请注意，此搜索是在两个不同的数组 left 和 right 上执行的，每个数组大约包含 75/2 个元素)

Left search-index:20 Div: 2
Left search-index:10 Div: 4
Left search-index:12 Div: 8
Left search-index:13 Div: 16
Left search-index:14 Div: 32
Left search-index:15 Div: 64
Left search-index:16 Div: 128
Left search-index:17 Div: 256
Left search-index:18 Div: 512
Right search-index:17 Div: 2
Right search-index:9 Div: 4
Right search-index:11 Div: 8
Right search-index:12 Div: 16
Right search-index:13 Div: 32
Right search-index:14 Div: 64
Right search-index:15 Div: 128
Right search-index:16 Div: 256
true
Left search-index:20 Div: 2
Left search-index:10 Div: 4
Left search-index:12 Div: 8
Left search-index:13 Div: 16
Left search-index:14 Div: 32
Left search-index:15 Div: 64
Left search-index:16 Div: 128
Left search-index:17 Div: 256
false
Left search-index:20 Div: 2
Left search-index:30 Div: 4
Left search-index:23 Div: 8
Left search-index:25 Div: 16
Right search-index:17 Div: 2
Right search-index:9 Div: 4
Right search-index:11 Div: 8
Right search-index:12 Div: 16
false

Answer 1

此实现具有二进制搜索的概念。二分查找维护两个边界:左边界和右边界，你只有一个边界。所以这可能会导致一些无限循环，当它回到一条线上时:

else index = index - index/div;

即index 是 100，你已经检查了 90，所以答案在 90 和 100 之间，但它会回落到 50 并且可以无限循环，因为它已经在这个区域。

编程中的很多错误并不那么容易发现:Nearly All Binary Searches and Mergesorts are Broken .

所以你可以使用标准方法(注意 pos 可以是负数):

int pos = Arrays.binarySearch(p);

它会给你一个需要的位置，答案是 (A[pos - 1], A[pos]) 或 (A[pos], A[pos + 1])

线性搜索也可以在这里工作，因为只有 10.000 个元素。

JavaDoc :

> Returns: 
> index of the search key, if it is contained in the array;
> otherwise, (-(insertion point) - 1). The insertion point is defined as
> the point at which the key would be inserted into the array: the index
> of the first element greater than the key, or a.length if all elements
> in the array are less than the specified key. Note that this
> guarantees that the return value will be >= 0 if and only if the key
> is found.