Елемент за претрагу у сортираној матрици
Задата сортирана матрица заједно са [][] величине н × м и цео број к утврди да ли је х присутно у матрици.
Матрица се сортира на следећи начин:
- Сваки ред се сортира по растућем редоследу.
- Први елемент сваког реда је већи или једнак последњем елементу претходног реда
(тј. мат[и][0] ≥ мат[и−1][м−1] за све 1 ≤ и < n).
Примери:
Улаз: к = 14 мат [][] = [[ 1 5 9]
[14 20 21]
[30 34 43]]
Излаз: истина
Објашњење: Вредност14је присутан у другом реду прве колоне матрице.Улаз: к = 42 мат [][] = [[ 1 5 9 11]
[14 20 21 26]
[30 34 43 50]]
Излаз: лажно
Објашњење: Вредност42се не појављује у матрици.
Садржај
- [Наивни приступ] Поређење са свим елементима – О(н × м) Време и О(1) Простор
- [Бољи приступ] Коришћење бинарне претраге двапут - О(лог н + лог м) време и О(1) простор
- [Очекивани приступ] Једнократно коришћење бинарне претраге - О(лог(н × м)) и О(1) размак
[Наивни приступ] Поређење са свим елементима – О(н × м) Време и О(1) Простор
C++Идеја је да се итерира кроз читаву матричну мат [][] и упореди сваки елемент са к. Ако се елемент поклапа са к, вратићемо тачно. У супротном на крају обиласка вратићемо фалсе.
#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
[Бољи приступ] Коришћење бинарне претраге двапут - О(лог н + лог м) време и О(1) простор
Прво лоцирамо ред у коме би циљни к могао бити коришћењем бинарне претраге, а затим поново примењујемо бинарну претрагу унутар тог реда. Да бисмо пронашли тачан ред, вршимо бинарну претрагу на првим елементима средњег реда.
Корак по корак имплементације:
=> Почните са ниским = 0 и високим = н - 1.
=> Ако је к мањи од првог елемента средњег реда (а[средина][0]), онда ће к бити мањи од свих елемената у редовима >= средина, тако да ажурирај хигх = мид - 1.
=> Ако је к већи од првог елемента средњег реда (а[мид][0]) онда ће к бити већи од свих елемената у редовима < mid so store the current mid row and update low = mid + 1.
Када пронађемо тачан ред, можемо применити бинарну претрагу унутар тог реда да бисмо тражили циљни елемент к.
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
[Очекивани приступ] Једнократно коришћење бинарне претраге - О(лог(н × м)) и О(1) размак
Идеја је да се дата матрица посматра као 1Д низ и примени само једно бинарно претраживање.
На пример, за матрицу величине н к м и можемо је сматрати 1Д низом величине н*м тада би први индекс био 0, а последњи индекс би н*м-1. Дакле, треба да извршимо бинарну претрагу од ниског = 0 до високог = (н*м-1).
Како пронаћи елемент у 2Д матрици који одговара индексу = средини?
C++Пошто ће сваки ред мат [][] имати м елемената тако да можемо пронаћи ред елемента као (средина / м) анд тхе колона елемента као (средњи % м) . Затим можемо да упоредимо к са арр[мид/м][мид%м] за сваки мид и завршимо нашу бинарну претрагу.
#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Креирај квиз
