Binary Search in 2D Array

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

algorithm multidimensional-array binary-search

Edit Report

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:

answered 2010-12-12T14:25:32.280

Binary Search in 2D Array

1 Answer

Your Answer