Binary Search in 2D Array

Question

I wonder, can binary search be applied on a 2D array?

• What would the conditions on the array be? Sorted on 2D??
• What would be the time complexity for it?
• How would the algorithm change the boundary of the search (minX,maxX,minY,maxY) ??

Edit:

Binary Search on 1D maintains 2 pointers minX and maxX.. It selects the middle index (minX+maxX)/2 and compare it with the search value, if greater then change maxX, else change minX... until minX>=maxX

Pseudo code for normal binary seacrh:

 min := 1;
  max := N; {array size: var A : array [1..N] of integer}
  repeat
    mid := min + (max - min) div 2;
    if x > A[mid] then
      min := mid + 1
    else 
      max := mid - 1;
  until (A[mid] = x) or (min > max);

Thanks

Answer 1

I solved it in a simple way in O(m + n) time complexity, where m = no. of rows and n = no. of columns.

The algorithm is simple: I started from top right corner (we can also start from bottom left corner) and move left if current element is greater than the value to be searched and bottom if current element is smaller than the value to be searched.

The java code is like:

public static int[] linearSearch(int[][] a, int value) {
    int i = 0, j = a[0].length - 1; // start from top right corner

    while (i < a.length && j >= 0) {
        if (a[i][j] == value) {
            return new int[]{i, j};
        } else if (a[i][j] > value) {
            j--; // move left
        } else {
            i++; // move down
        }
    }
    // element not found
    return new int[]{-1, -1};

}

Gist

You can further reduce the time complexity by using a method called Improved Binary Partition.

Answer 2

I thought about this problem last year... So, I'd choosed this approach:

Consider your 2D-array represents points in a plane. For example, your element A[i][j] represents a point with x = i and y = j. To use binary search on the plane I sort all points using this condition:

point p1 < p2 if and only if:

• (x-coordinate of p1) < (x-coordinate of p2)
• (x-coordinate of p1) = (x-coordinate of p2) and (y-coordinate of p1) < (y-coordinate of p2)

Othwerwise p1 >= p2.

Now, if we look to our 2D-array, elements in 2nd row should be greater than elements in 1st row. In same row elements sorted as usual (according to their column number).

In another words:

• A[i][j] > A[k][j] if and only if (i>k). (in different rows and in same column)
• A[i][j] > A[i][k] if and only if (j>k). (in the same row and different columns)

Consider your array has N rows and M columns. Now you should (temporarly) transform your 2D array to 1D array using this formula (T - temporary array):

for i:=0 to N-1 do
    for j:=0 to M-1 do
        T[i*N + j]:= A[i][j];

Now you have 1D array. Sort it in usual way. And now you can search in it using simple binary search algorithm.

Or you can transform your sorted array back to 2D array using this formula:

for i:=0 to N*M-1 do
    A[i div N][i - (i div N)*N]:= T[i];

And use two binary searches:

One search by x-coordinate (by rows in our meaning), another one by y-coordinate (by columns in our meaning) for elements in same row.

In another words, when you calculate mid = mid + (max - min) div 2, you can compare element A[mid][0] with your key-element(in your code it has x name) and when you find row with your element, you can call another binary search in this row (binary search in A[mid]).

Complexity for both methods:

• for simple binary search in trasformed array: log(N*M)
• for two binary searches in 2D array: log(N) for outer search (in rows) + log(M) for inner search (in columns).

Using the properties of logarithm function we can simplify last expression: log(N) + log(M) = log(N*M).

So, we proved, that both methods has same complexity and doesn't matter, which one to use.

But, if it's not hard to you, I suggest you simply transform your array to 1-D and use simple binary search (it's very simple and easy to debug and check).