Binary Search in 2D Array

I wonder, can binary search be applied on a 2D ar开发者_开发知识库ray?

• 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

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.

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).

Binary Search works in the divide and conquer way,

int r = arr.length; // ROW Count
int c = arr[0].length; // Column Count
int start = 0; // Initialize with the 0
int end = r*c-1; // Last Index

We will keep iterating the while loop, each time we updating the start and end index as per requirements..
while(start <= end){

int mid = (start+end)/2;
int midX = mid/c;
int midY = mid%c;

If the current value is equals to the search element then we just have to print and return it.

if(arr[midX][midY] == searchElement){
return true;
}

If the current value is smaller then the search element then we just have to update the mid value by mid = mid + 1

if(arr[midX][midY] < searchElement){
start = mid+1;
}

If the current value is grater than the search element then we just have to update the mid value by mid = mid - 1

else{
end = mid-1;
}

Binary search requires that your array be sorted. Sorting, in turn, requires a total ordering relationship on the array elements. In 1-D it's fairly easy to understand what this means. I think you will have to define a 1-D index into your 2-D array and ensure that the array elements are sorted along that index.

You have a variety of 1-D indexing schemes to choose from, essentially any space-filling curve will do. The obvious ones which come to mind are:

• Start with the first element, read along each row, at the end of each row go to the first element in the next row.
• Same, replace row by column.
• A diagonalisation, in which you read each diagonal in turn.

Like @Bart Kiers, I don't understand your 2nd point.

Just pretend it's a 1D array and calculate the correct row and column as you divide and conquer:

/**
* @param grid {[[number]]} A 2D NxM grid of numbers
* @param targetValue {number} The target value to search
* @return {[number]} A list containing the row and column. For example, [0,5] means row 0 column 5 
*/
function search (grid, targetValue) {
    let rows = grid.length;
    let cols = grid[0].length;

    let leftBound = 0;
    let rightBound = rows * cols - 1;

    while (true) {
        let currentIndex = parseInt((leftBound + rightBound) / 2);
        let currentRow = parseInt(currentIndex / cols);
        let currentColumn = currentIndex % cols;
        let currentValue = grid[currentRow][currentColumn];

        if (currentValue === targetValue) {
            return [currentRow, currentColumn];
        }
        else if (rightBound <= leftBound) {
            return [-1, -1];
        }
        else if (currentValue < targetValue) {
            leftBound = currentIndex + 1;
        }
        else {
            rightBound = currentIndex - 1;
        }
    }

}

search([[11,12,15,23],[25,28,31,32],[35,45,47,47],[50,51,55,56],[65,65,78,88]], 45);

No, it is not possible to apply a binary search on a 2D array.

Requirements for a binary search:

Requirement 1: Items are sorted

In a 1D array it is clear what that means. But what does that exactly mean for a 2D array?

Requirement 2: 2 directions

A binary search requires that when ever you pick an item in it, you can go into 2 directions from there.

Because of the sorting, whenever you pick an item, the item supplies enough information to know in which of the 2 direction you need to continue your search. That allows to split the search scope in 2 parts and that's why we call it binary.

If you pick an item in a 2D array, there are 4 possible directions (or even more: you could move diagonally as well). Even if all items are sorted in someway the information in one item can't tell you which direction you have to go and how to split the array based on that.

A binary search will be possible only if you can convert the 2D array into a sorted 1D array. If a function can be defined that combines the indexes x and y into an index i for a sorted virtual 1D array containing all items in the 2D array and x and y can be calculated back from i, then you can use a binary search on that virtual 1D array. And that function depends on how the items in the 2D array are sorted. But that means you are doing a binary search on a 1D array not on a 2D array!

This is the binary search solution and works for all test cases.

bool searchMatrix(vector<vector<int>>& matrix, int target) {
    int h = 0, w = matrix[0].size(), x;
    while(h < matrix.size() && w && (x = matrix[h][w-1]) != target) {
        if (x > target) w--;
        else h++;
    }
    return x == target;
}

You can transform 2D array into 1D array and do the binary search here. Complexity is O(log(m * n)) for mxn array.