정렬된 행렬의 요소 검색
정렬된 행렬이 주어지면 [][]와 함께 크기 n × m 및 정수 엑스 x가 행렬에 존재하는지 확인합니다.
행렬은 다음과 같은 방식으로 정렬됩니다.
- 각 행은 오름차순으로 정렬됩니다.
- 각 행의 첫 번째 요소는 이전 행의 마지막 요소보다 크거나 같습니다.
(즉, 모든 1 ≤ i에 대해 mat[i][0] ≥ mat[i−1][m−1] < n).
예:
입력: x = 14 매트[][] = [[ 1 5 9]
[14 20 21]
[30 34 43]]
산출: 진실
설명: 가치14행렬의 두 번째 행 첫 번째 열에 존재합니다.입력: x = 42 매트[][] = [[ 1 5 9 11]
[14 20 21 26]
[30 34 43 50]]
산출: 거짓
설명: 가치42매트릭스에는 나타나지 않습니다.
목차
- [순진한 접근 방식] 모든 요소 비교 – O(n × m) 시간 및 O(1) 공간
- [더 나은 접근 방식] 이진 검색을 두 번 사용 - O(log n + log m) 시간 및 O(1) 공간
- [예상 접근법] 이진 검색을 한 번만 사용 - O(log(n × m)) 및 O(1) 공간
[순진한 접근 방식] 모든 요소 비교 - O(n × m) 시간 및 O(1) 공간
C++아이디어는 전체 행렬 mat[][]를 반복하고 각 요소를 x와 비교하는 것입니다. 요소가 x와 일치하면 true를 반환합니다. 그렇지 않으면 순회가 끝나면 false를 반환합니다.
#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' );
산출
true
[더 나은 접근 방식] 이진 검색을 두 번 사용 - O(log n + log m) 시간 및 O(1) 공간
먼저 이진 검색을 사용하여 대상 x가 있을 수 있는 행을 찾은 다음 해당 행 내에서 다시 이진 검색을 적용합니다. 올바른 행을 찾기 위해 중간 행의 첫 번째 요소에 대해 이진 검색을 수행합니다.
단계별 구현:
=> 낮은 = 0, 높은 = n - 1로 시작합니다.
=> x가 중간 행의 첫 번째 요소(a[mid][0])보다 작으면 x는 >= mid 행의 모든 요소보다 작으므로 high = mid - 1로 업데이트됩니다.
=> x가 중간 행의 첫 번째 요소(a[mid][0])보다 크면 x는 행의 모든 요소보다 큽니다. < mid so store the current mid row and update low = mid + 1.
올바른 행을 찾으면 해당 행 내에서 이진 검색을 적용하여 대상 요소 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' );
산출
true
[예상 접근법] 이진 검색을 한 번만 사용 - O(log(n × m)) 및 O(1) 공간
아이디어는 주어진 행렬을 1D 배열로 간주하고 하나의 이진 검색만 적용하는 것입니다.
예를 들어 n x m 크기의 행렬의 경우 이를 n*m 크기의 1D 배열로 간주하면 첫 번째 인덱스는 0이 되고 마지막 인덱스는 n*m-1이 됩니다. 따라서 low = 0부터 high = (n*m-1)까지 이진 검색을 수행해야 합니다.
index = mid에 해당하는 2D 행렬의 요소를 찾는 방법은 무엇입니까?
C++mat[][]의 각 행에는 m개의 요소가 있으므로 다음을 찾을 수 있습니다. 열 요소의 (중/m) 그리고 열 요소의 (중간%m) . 그런 다음 x를 각 mid에 대해 arr[mid/m][mid%m]과 비교하고 이진 검색을 완료할 수 있습니다.
#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' );
산출
true퀴즈 만들기
