عنصر البحث في مصفوفة مرتبة
نظرا لمصفوفة مرتبة جنبا إلى جنب مع[][] بالحجم n × m وعدد صحيح س تحديد ما إذا كان x موجودًا في المصفوفة.
يتم فرز المصفوفة على النحو التالي:
- يتم فرز كل صف بترتيب متزايد.
- العنصر الأول في كل صف أكبر من أو يساوي العنصر الأخير في الصف السابق
(أي حصيرة [i] [0] ≥ حصيرة [i−1] [m−1] للجميع 1 ≥ i < 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لا يظهر في المصفوفة.
جدول المحتويات
- [نهج ساذج] المقارنة مع جميع العناصر - O(n × m) الزمن وO(1) الفضاء
- [نهج أفضل] استخدام البحث الثنائي مرتين - O(log n + log m) الوقت وO(1) الفضاء
- [النهج المتوقع] استخدام البحث الثنائي مرة واحدة - O(log(n × m)) وO(1) Space
[نهج ساذج] المقارنة مع جميع العناصر - O(n × m) الزمن وO(1) الفضاء
C++تتمثل الفكرة في التكرار خلال حصيرة المصفوفة بأكملها[]] ومقارنة كل عنصر بـ x. إذا كان العنصر مطابقًا لـ x فسنعود صحيحًا. وإلا في نهاية الاجتياز سنعود خطأً.
#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) Space
تتمثل الفكرة في اعتبار المصفوفة المعطاة مصفوفة أحادية الأبعاد وتطبيق بحث ثنائي واحد فقط.
على سبيل المثال، بالنسبة لمصفوفة بحجم n x m ويمكننا اعتبارها مصفوفة أحادية الأبعاد بحجم n*m، فسيكون الفهرس الأول هو 0 والفهرس الأخير سيكون n*m-1. لذلك نحن بحاجة إلى إجراء بحث ثنائي من منخفض = 0 إلى مرتفع = (n*m-1).
كيفية العثور على العنصر في مصفوفة ثنائية الأبعاد المقابلة للفهرس = منتصف؟
C++نظرًا لأن كل صف من mat[]] سيحتوي على عناصر m حتى نتمكن من العثور على صف للعنصر كما (منتصف / م) و عمود للعنصر كما (منتصف٪ م) . ثم يمكننا مقارنة x مع 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إنشاء اختبار
