Søgeelement i en sorteret matrix
Givet en sorteret matrix sammen med[][] af størrelse n × m og et heltal x afgøre om x er til stede i matrixen.
Matrixen er sorteret på følgende måde:
- Hver række sorteres i stigende rækkefølge.
- Det første element i hver række er større end eller lig med det sidste element i den foregående række
(dvs. mat[i][0] ≥ mat[i−1][m−1] for alle 1 ≤ i < n).
Eksempler:
Input: x = 14 mat[][] = [[ 1 5 9]
[14 20 21]
[30 34 43]]
Produktion: ægte
Forklaring: Værdien14er til stede i den anden række første kolonne i matrixen.Input: x = 42 mat[][] = [[ 1 5 9 11]
[14 20 21 26]
[30 34 43 50]]
Produktion: falsk
Forklaring: Værdien42vises ikke i matrixen.
Indholdsfortegnelse
- [Naiv tilgang] Sammenligning med alle elementer – O(n × m) Tid og O(1) Rum
- [Bedre tilgang] Brug af binær søgning to gange - O(log n + log m) Tid og O(1) Mellemrum
- [Forventet tilgang] Brug af binær søgning én gang - O(log(n × m)) og O(1) mellemrum
[Naiv tilgang] Sammenligning med alle elementer – O(n × m) Tid og O(1) Rum
C++Ideen er at iterere gennem hele matrixmåtten[][] og sammenligne hvert element med x. Hvis et element matcher x'et, returnerer vi sand. Ellers vil vi returnere falsk ved slutningen af gennemgangen.
#include #include using namespace std ; bool searchMatrix ( vector < vector < int >>& mat int x ) { int n = mat . size (); int m = mat [ 0 ]. size (); // traverse every element in the matrix for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < m ; j ++ ) { if ( mat [ i ][ j ] == x ) return true ; } } return false ; } int main () { vector < vector < int >> mat = { { 1 5 9 } { 14 20 21 } { 30 34 43 } }; int x = 14 ; cout < < ( searchMatrix ( mat x ) ? 'true' : 'false' ) < < endl ; }
Java class GfG { public static boolean searchMatrix ( int [][] mat int x ) { int n = mat . length ; int m = mat [ 0 ] . length ; // traverse every element in the matrix for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < m ; j ++ ) { if ( mat [ i ][ j ] == x ) return true ; } } return false ; } public static void main ( String [] args ) { int [][] mat = { { 1 5 9 } { 14 20 21 } { 30 34 43 } }; int x = 14 ; System . out . println ( searchMatrix ( mat x ) ? 'true' : 'false' ); } }
Python def searchMatrix ( mat x ): n = len ( mat ) m = len ( mat [ 0 ]) # traverse every element in the matrix for i in range ( n ): for j in range ( m ): if mat [ i ][ j ] == x : return True return False if __name__ == '__main__' : mat = [ [ 1 5 9 ] [ 14 20 21 ] [ 30 34 43 ] ] x = 14 print ( 'true' if searchMatrix ( mat x ) else 'false' )
C# using System ; class GfG { public static bool searchMatrix ( int [][] mat int x ) { int n = mat . Length ; int m = mat [ 0 ]. Length ; // traverse every element in the matrix for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < m ; j ++ ) { if ( mat [ i ][ j ] == x ) return true ; } } return false ; } public static void Main ( string [] args ) { int [][] mat = new int [][] { new int [] { 1 5 9 } new int [] { 14 20 21 } new int [] { 30 34 43 } }; int x = 14 ; Console . WriteLine ( searchMatrix ( mat x ) ? 'true' : 'false' ); } }
JavaScript function searchMatrix ( mat x ) { let n = mat . length ; let m = mat [ 0 ]. length ; // traverse every element in the matrix for ( let i = 0 ; i < n ; i ++ ) { for ( let j = 0 ; j < m ; j ++ ) { if ( mat [ i ][ j ] === x ) return true ; } } return false ; } // Driver Code let mat = [ [ 1 5 9 ] [ 14 20 21 ] [ 30 34 43 ] ]; let x = 14 ; console . log ( searchMatrix ( mat x ) ? 'true' : 'false' );
Produktion
true
[Bedre tilgang] Brug af binær søgning to gange - O(log n + log m) Tid og O(1) Mellemrum
Først finder vi rækken, hvor målet x kan være ved at bruge binær søgning, og derefter anvender vi binær søgning igen inden for den række. For at finde den korrekte række udfører vi binær søgning på de første elementer i den midterste række.
Trin for trin implementeringer:
=> Start med lav = 0 og høj = n - 1.
=> Hvis x er mindre end det første element i den midterste række (a[mid][0]), så vil x være mindre end alle elementer i rækkerne >= midt, så opdater høj = midt - 1.
=> Hvis x er større end det første element i den midterste række (a[mid][0]), vil x være større end alle elementer i rækkerne < mid so store the current mid row and update low = mid + 1.
Når vi har fundet den rigtige række, kan vi anvende binær søgning i den række for at søge efter målelementet x.
C++ #include #include using namespace std ; // function to binary search for x in arr[] bool search ( vector < int > & arr int x ) { int lo = 0 hi = arr . size () - 1 ; while ( lo <= hi ) { int mid = ( lo + hi ) / 2 ; if ( x == arr [ mid ]) return true ; if ( x < arr [ mid ]) hi = mid - 1 ; else lo = mid + 1 ; } return false ; } // function to search element x in fully // sorted matrix bool searchMatrix ( vector < vector < int >> & mat int x ) { int n = mat . size () m = mat [ 0 ]. size (); int lo = 0 hi = n - 1 ; int row = -1 ; while ( lo <= hi ) { int mid = ( lo + hi ) / 2 ; // if the first element of mid row is equal to x // return true if ( x == mat [ mid ][ 0 ]) return true ; // if x is greater than first element of mid row // store the mid row and search in lower half if ( x > mat [ mid ][ 0 ]) { row = mid ; lo = mid + 1 ; } // if x is smaller than first element of mid row // search in upper half else hi = mid - 1 ; } // if x is smaller than all elements of mat[][] if ( row == -1 ) return false ; return search ( mat [ row ] x ); } int main () { vector < vector < int >> mat = {{ 1 5 9 } { 14 20 21 } { 30 34 43 }}; int x = 14 ; if ( searchMatrix ( mat x )) cout < < 'true' ; else cout < < 'false' ; return 0 ; }
Java class GfG { // function to binary search for x in arr[] static boolean search ( int [] arr int x ) { int lo = 0 hi = arr . length - 1 ; while ( lo <= hi ) { int mid = ( lo + hi ) / 2 ; if ( x == arr [ mid ] ) return true ; if ( x < arr [ mid ] ) hi = mid - 1 ; else lo = mid + 1 ; } return false ; } // function to search element x in fully // sorted matrix static boolean searchMatrix ( int [][] mat int x ) { int n = mat . length m = mat [ 0 ] . length ; int lo = 0 hi = n - 1 ; int row = - 1 ; while ( lo <= hi ) { int mid = ( lo + hi ) / 2 ; // if the first element of mid row is equal to x // return true if ( x == mat [ mid ][ 0 ] ) return true ; // if x is greater than first element of mid row // store the mid row and search in lower half if ( x > mat [ mid ][ 0 ] ) { row = mid ; lo = mid + 1 ; } // if x is smaller than first element of mid row // search in upper half else hi = mid - 1 ; } // if x is smaller than all elements of mat[][] if ( row == - 1 ) return false ; return search ( mat [ row ] x ); } public static void main ( String [] args ) { int [][] mat = { { 1 5 9 } { 14 20 21 } { 30 34 43 } }; int x = 14 ; if ( searchMatrix ( mat x )) System . out . println ( 'true' ); else System . out . println ( 'false' ); } }
Python # function to binary search for x in arr[] def search ( arr x ): lo = 0 hi = len ( arr ) - 1 while lo <= hi : mid = ( lo + hi ) // 2 if x == arr [ mid ]: return True if x < arr [ mid ]: hi = mid - 1 else : lo = mid + 1 return False # function to search element x in fully # sorted matrix def searchMatrix ( mat x ): n = len ( mat ) m = len ( mat [ 0 ]) lo = 0 hi = n - 1 row = - 1 while lo <= hi : mid = ( lo + hi ) // 2 # if the first element of mid row is equal to x # return true if x == mat [ mid ][ 0 ]: return True # if x is greater than first element of mid row # store the mid row and search in lower half if x > mat [ mid ][ 0 ]: row = mid lo = mid + 1 # if x is smaller than first element of mid row # search in upper half else : hi = mid - 1 # if x is smaller than all elements of mat[][] if row == - 1 : return False return search ( mat [ row ] x ) if __name__ == '__main__' : mat = [[ 1 5 9 ] [ 14 20 21 ] [ 30 34 43 ]] x = 14 if searchMatrix ( mat x ): print ( 'true' ) else : print ( 'false' )
C# using System ; class GfG { // function to binary search for x in arr[] static bool Search ( int [] arr int x ) { int lo = 0 hi = arr . Length - 1 ; while ( lo <= hi ) { int mid = ( lo + hi ) / 2 ; if ( x == arr [ mid ]) return true ; if ( x < arr [ mid ]) hi = mid - 1 ; else lo = mid + 1 ; } return false ; } // function to search element x in fully // sorted matrix static bool SearchMatrix ( int [][] mat int x ) { int n = mat . Length m = mat [ 0 ]. Length ; int lo = 0 hi = n - 1 ; int row = - 1 ; while ( lo <= hi ) { int mid = ( lo + hi ) / 2 ; // if the first element of mid row is equal to x // return true if ( x == mat [ mid ][ 0 ]) return true ; // if x is greater than first element of mid row // store the mid row and search in lower half if ( x > mat [ mid ][ 0 ]) { row = mid ; lo = mid + 1 ; } // if x is smaller than first element of mid row // search in upper half else hi = mid - 1 ; } // if x is smaller than all elements of mat[][] if ( row == - 1 ) return false ; return Search ( mat [ row ] x ); } static void Main ( string [] args ) { int [][] mat = new int [][] { new int [] { 1 5 9 } new int [] { 14 20 21 } new int [] { 30 34 43 } }; int x = 14 ; if ( SearchMatrix ( mat x )) Console . WriteLine ( 'true' ); else Console . WriteLine ( 'false' ); } }
JavaScript // function to binary search for x in arr[] function search ( arr x ) { let lo = 0 hi = arr . length - 1 ; while ( lo <= hi ) { let mid = Math . floor (( lo + hi ) / 2 ); if ( x === arr [ mid ]) return true ; if ( x < arr [ mid ]) hi = mid - 1 ; else lo = mid + 1 ; } return false ; } // function to search element x in fully // sorted matrix function searchMatrix ( mat x ) { let n = mat . length m = mat [ 0 ]. length ; let lo = 0 hi = n - 1 ; let row = - 1 ; while ( lo <= hi ) { let mid = Math . floor (( lo + hi ) / 2 ); // if the first element of mid row is equal to x // return true if ( x === mat [ mid ][ 0 ]) return true ; // if x is greater than first element of mid row // store the mid row and search in lower half if ( x > mat [ mid ][ 0 ]) { row = mid ; lo = mid + 1 ; } // if x is smaller than first element of mid row // search in upper half else hi = mid - 1 ; } // if x is smaller than all elements of mat[][] if ( row === - 1 ) return false ; return search ( mat [ row ] x ); } // Driver code const mat = [ [ 1 5 9 ] [ 14 20 21 ] [ 30 34 43 ] ]; const x = 14 ; if ( searchMatrix ( mat x )) console . log ( 'true' ); else console . log ( 'false' );
Produktion
true
[Forventet tilgang] Brug af binær søgning én gang - O(log(n × m)) og O(1) mellemrum
Ideen er at betragte den givne matrix som 1D-array og kun anvende én binær søgning.
For eksempel for en matrix af størrelse n x m, og vi kan betragte det som en 1D-array af størrelse n*m, så ville det første indeks være 0, og det sidste indeks ville være n*m-1. Så vi skal lave binær søgning fra lav = 0 til høj = (n*m-1).
Hvordan finder man elementet i 2D matrix svarende til index = mid?
C++Da hver række af måtter[][] vil have m elementer, så vi kan finde række af elementet som (midt/m) og den kolonne af elementet som (midt % m) . Så kan vi sammenligne x med arr[midt/m][mid%m] for hver midte og fuldføre vores binære søgning.
#include #include using namespace std ; bool searchMatrix ( vector < vector < int >>& mat int x ) { int n = mat . size () m = mat [ 0 ]. size (); int lo = 0 hi = n * m - 1 ; while ( lo <= hi ) { int mid = ( lo + hi ) / 2 ; // find row and column of element at mid index int row = mid / m ; int col = mid % m ; // if x is found return true if ( mat [ row ][ col ] == x ) return true ; // if x is greater than mat[row][col] search // in right half if ( mat [ row ][ col ] < x ) lo = mid + 1 ; // if x is less than mat[row][col] search // in left half else hi = mid - 1 ; } return false ; } int main () { vector < vector < int >> mat = {{ 1 5 9 } { 14 20 21 } { 30 34 43 }}; int x = 14 ; if ( searchMatrix ( mat x )) cout < < 'true' ; else cout < < 'false' ; return 0 ; }
Java class GfG { static boolean searchMatrix ( int [][] mat int x ) { int n = mat . length m = mat [ 0 ] . length ; int lo = 0 hi = n * m - 1 ; while ( lo <= hi ) { int mid = ( lo + hi ) / 2 ; // find row and column of element at mid index int row = mid / m ; int col = mid % m ; // if x is found return true if ( mat [ row ][ col ] == x ) return true ; // if x is greater than mat[row][col] search // in right half if ( mat [ row ][ col ] < x ) lo = mid + 1 ; // if x is less than mat[row][col] search // in left half else hi = mid - 1 ; } return false ; } public static void main ( String [] args ) { int [][] mat = {{ 1 5 9 } { 14 20 21 } { 30 34 43 }}; int x = 14 ; if ( searchMatrix ( mat x )) System . out . println ( 'true' ); else System . out . println ( 'false' ); } }
Python def searchMatrix ( mat x ): n = len ( mat ) m = len ( mat [ 0 ]) lo hi = 0 n * m - 1 while lo <= hi : mid = ( lo + hi ) // 2 # find row and column of element at mid index row = mid // m col = mid % m # if x is found return true if mat [ row ][ col ] == x : return True # if x is greater than mat[row][col] search # in right half if mat [ row ][ col ] < x : lo = mid + 1 # if x is less than mat[row][col] search # in left half else : hi = mid - 1 return False if __name__ == '__main__' : mat = [[ 1 5 9 ] [ 14 20 21 ] [ 30 34 43 ]] x = 14 if searchMatrix ( mat x ): print ( 'true' ) else : print ( 'false' )
C# using System ; class GfG { // function to search for x in the matrix // using binary search static bool searchMatrix ( int [] mat int x ) { int n = mat . GetLength ( 0 ) m = mat . GetLength ( 1 ); int lo = 0 hi = n * m - 1 ; while ( lo <= hi ) { int mid = ( lo + hi ) / 2 ; // find row and column of element at mid index int row = mid / m ; int col = mid % m ; // if x is found return true if ( mat [ row col ] == x ) return true ; // if x is greater than mat[row col] search // in right half if ( mat [ row col ] < x ) lo = mid + 1 ; // if x is less than mat[row col] search // in left half else hi = mid - 1 ; } return false ; } static void Main () { int [] mat = { { 1 5 9 } { 14 20 21 } { 30 34 43 } }; int x = 14 ; if ( searchMatrix ( mat x )) Console . WriteLine ( 'true' ); else Console . WriteLine ( 'false' ); } }
JavaScript function searchMatrix ( mat x ) { let n = mat . length m = mat [ 0 ]. length ; let lo = 0 hi = n * m - 1 ; while ( lo <= hi ) { let mid = Math . floor (( lo + hi ) / 2 ); // find row and column of element at mid index let row = Math . floor ( mid / m ); let col = mid % m ; // if x is found return true if ( mat [ row ][ col ] === x ) return true ; // if x is greater than mat[row][col] search // in right half if ( mat [ row ][ col ] < x ) lo = mid + 1 ; // if x is less than mat[row][col] search // in left half else hi = mid - 1 ; } return false ; } // Driver Code let mat = [[ 1 5 9 ] [ 14 20 21 ] [ 30 34 43 ]]; let x = 14 ; if ( searchMatrix ( mat x )) console . log ( 'true' ); else console . log ( 'false' );
Produktion
trueOpret quiz
