CODEWITHSUNDEEP
searchmatrix
user1399689
user1399689

Reputation: 31

lookup for certain value in sorted matrix(mXn) with time complexity O(lgm) + O(lgn)

The matrix A is sorted by row and column where A[i][j] < A[i][j+1] and A[i][j] < A[i+1][j]. An additional information is that the first element of each row is smaller than the last element of the previous row, for example :

⎡1  3   5  17⎤
⎢2  4   6  18⎥
⎣7  9  11  20⎦

And I am confused about what role this additional information plays in determining the O(lgn) complexity.

I could come up with O(m) + O(n) as the following:

int search(int mat[4][4], int n, int x)
{
   int i = 0, j = n-1;  //set indexes for top right element
   while ( i < n && j >= 0 )
   {
       if ( mat[i][j] == x )
       {
          printf("\n Found at %d, %d", i, j);
          return 1;
       }
       if ( mat[i][j] > x )
           j--;
       else //  if mat[i][j] < x
           i++;
       }

       printf("\n Element not found");
       return 0;  // if ( i==n || j== -1 )
  }

But I do not think I have used the information : the first element of each row is smaller than the last element of the previous row

Could anyone plz give me some hints? Plus this is not homework. Thank you!

Upvotes: 3

Views: 412

Answers (1)

acattle
acattle

Reputation: 3113

What you're currently doing is an exhaustive search (i.e. checking every element once), thus O(n*m). You aren't taking advantage of the sorted nature of the matrix.

Given a sorted list, Binary Search lets you search in O(lg n). Basically, you check the middle element of your list. If it's greater than your target then you know you can ignore the second half of the list. Repeat this process, halfing your search space each time, until you find the element or your search space equals 1 item. In Python code:

import math

def binSearch(value, data):
    bottom = 0 #first entry
    top = len(data) -1 #last entry

    while bottom <= top: #if bottom ever becomes greater than top then the object is not in the list
        i = int(bottom + math.floor((top - bottom)/2)) #find the mid-point
        if data[i] == value: #we found it
            return i
        elif data[i] > value:
            top = i - 1 #value must be before i
        else:
            bottom = i + 1 #value must be after i

    return None #not found

Now, think about what information you can gather from the matrix structure. You know that given a n x m matrix mat sorted as you desribed, for any row i, mat[i][0] is the lowest items in the row and mat[i][n] is the highest. Similarly, for any column j, mat[0][j] is the lowest value fo that column and mat[m][j] is the highest. That means that if mat[i][0] <= value <= mat[i][n] is not true then value cannot be in row i. Similarly, if mat[0][j] <= value <= mat[m][j] is not true then value cannot be in column j.

So the obvious improvement is, for each row that could possibly contain the value, do a binary search.

for row in mat:
    if (row[0] <= value) AND (row[len(row) - 1] >= value): #if the value could possibly be in the row
        result = binSearch(value, row)

        if result: #if we found it
            return result

binSearch() is O(lg m). Worst case scenario is performing binSearch() on every row, thus O(n * lg m).

I was trying to implement a O(lg n * lg m) solution but I can't figure it out. The problem is that I can only eliminate the top left and bottom right corners of the matrix. I can't eliminate the bottom left or top right.

Upvotes: 1

Related Questions