Performing binary-search for points intervals

Question

I'm going to explain my problem trying to be as clear as I can. Point[] right is a ordered array of points, each Point object is a couple Long x, y.

Now, this is my goal. Given a Point p with its p.y coordinate, I have to find a couple of points Point p1, p2 in which (according to y coordinates) p is included, obviously using binary search. Here's my iterative implementation.

        /* 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;
        }

Now, questions:

1. Is this actually a binary search?
2. Could div suffer from overflow? I know that at runtime it throws an exception, but I don't know what and by who. (This issue happens on SPOJ submission and the only information I have is NZEC Runtime Error).
3. There's a way to improve performance? I'm expecting an array with 5000-10000 points.

I tried with a 75+ entries array and there is a trace of the execution. (Note that this search is performed on two different arrays left and right and each one contains 75/2 elements circa)

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

I wrote a new version with a strict binary search. What do you think? It keeps returning correct values, but doesn't work on SPOJ.

    low = 0; high = right.length - 1;
    mid = 0;

    while(low <= high) {
        mid = (low + high) >>> 1;
        System.out.println("MID: "+mid);
        c1 = right[mid].y;
        c2 = right[mid+1].y;

        if(py >= c1 && py <= c2) {
            p3 = right[mid];
            p4 = right[mid +1];
            break;
        }

        else if(py < c1)
            high = mid - 1;

        else
            low = mid + 1;
    }

Answer 2

This implementation has an idea of a binary search. Binary search maintains two borders: left and right, you only have one. So this could lead to some infinite cycles, when it falls back in a line:

else index = index - index/div;

I.e. index is 100, you already checked 90, so the answer is between 90 and 100, but it will fall back to 50 and could loop infinitely as it already had been in this area.

Many errors in programming are not that easy to find: Nearly All Binary Searches and Mergesorts are Broken.

So you could use a standard method (note that pos can be negative):

int pos = Arrays.binarySearch(p);

It will give you a needed position and the answer is either pair (A[pos - 1], A[pos]) or (A[pos], A[pos + 1])

Linear search could also work here, as there are only 10.000 elements.

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.

Answer 3

the only way for index/div==0 to be is true is when index is 0 thus index=index-1 will result in -1 value which is an illegal index or index is smaller than div big time.
One important thing in Java an array's index and length are int not long