Geek asks and answers

Search for a specific value in a sorted matrix (mXn) with time complexity O (lgm) + O (lgn)

Matrix A is sorted by row and column, where A [i] [j] A [i] [j + 1] and A [i] [j] A [i + 1] [J]. Additional information is that the first element of each row is less than the last element of the previous row, for example:

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

And I'm confused about the role this additional information plays in determining the complexity of O (lgn).

I could find O (m) + O (n) as follows:

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 don’t think I used the information: the first element of each row is less than the last element of the previous row

Can anyone plz give me some advice? Plus, this is not homework. Thank!

+3
source share
1 answer

, , - (.. ), , O (n * m). .

, Binary Search O (lg n). . , , , . , , 1 . Python:

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

, . , , n x m mat, , i, mat[i][0] , mat[i][n] . , j, mat[0][j] fo , mat[m][j] . , mat[i][0] <= value <= mat[i][n] , i. , mat[0][j] <= value <= mat[m][j] , j.

, , , , .

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() - O (lg m). binSearch() , , O (n * lg m).

O (lg n * lg m), . , . .

+1

More articles:


All Articles