logo

TechCodeview

Vyhľadávací prvok v triedenej matici

Daná triedená matica spolu s[][] veľkosti n × m a celé číslo x určiť, či je x prítomné v matici.
Matica je triedená nasledujúcim spôsobom:

  • Každý riadok je zoradený v rastúcom poradí.
  • Prvý prvok každého riadku je väčší alebo rovný poslednému prvku predchádzajúceho riadka
    (t. j. mat[i][0] ≥ mat[i−1][m−1] pre všetky 1 ≤ i< n).

Príklady:

Vstup: x = 14 mat[][] = [[ 1 5 9]
[14 20 21]
[30 34 43]]
výstup: pravda
Vysvetlenie: Hodnota14je prítomný v druhom riadku, prvom stĺpci matice.



Vstup: x = 42 mat[][] = [[ 1 5 9 11]
[14 20 21 26]
[30 34 43 50]]
výstup: falošné
Vysvetlenie: Hodnota42sa v matrici neobjaví.

Obsah

[Naivný prístup] Porovnanie so všetkými prvkami – O(n × m) Čas a O(1) Priestor

Ide o iteráciu celej matrice[][] a porovnanie každého prvku s x. Ak sa prvok zhoduje s x, vrátime hodnotu true. V opačnom prípade na konci prechodu vrátime hodnotu false.

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');

Výstup 
true

[Lepší prístup] Použitie binárneho vyhľadávania dvakrát - O(log n + log m) Čas a O(1) Priestor

Najprv pomocou binárneho vyhľadávania nájdeme riadok, kde by mohol byť cieľ x, a potom znova použijeme binárne vyhľadávanie v tomto riadku. Aby sme našli správny riadok, vykonáme binárne vyhľadávanie na prvých prvkoch stredného riadku.

Krok za krokom implementácie:

=> Začnite s nízkym = 0 a vysokým = n - 1.
=> Ak je x menšie ako prvý prvok stredného riadku (a[mid][0]), potom x bude menšie ako všetky prvky v riadkoch >= mid, takže aktualizujte high = mid - 1.
=> Ak je x väčšie ako prvý prvok stredného riadku (a[mid][0]), potom x bude väčšie ako všetky prvky v riadkoch< mid so store the current mid row and update low = mid + 1.

Keď nájdeme správny riadok, môžeme použiť binárne vyhľadávanie v tomto riadku na vyhľadanie cieľového prvku 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');

Výstup 
true

[Očakávaný prístup] Použitie binárneho vyhľadávania raz – O(log(n × m)) a O(1) Priestor

Cieľom je považovať danú maticu za 1D pole a použiť iba jedno binárne vyhľadávanie.
Napríklad pre maticu veľkosti n x m a môžeme ju považovať za 1D pole veľkosti n*m, potom prvý index bude 0 a posledný index bude n*m-1. Takže musíme vykonať binárne vyhľadávanie od low = 0 po high = (n*m-1).

Ako nájsť prvok v 2D matici zodpovedajúci indexu = stred?

Pretože každý riadok rohože[][] bude mať m prvkov, takže môžeme nájsť riadok prvku ako (stred / m) a stĺpec prvku ako (stred % m) . Potom môžeme porovnať x s arr[mid/m][mid%m] pre každý stred a dokončiť naše binárne vyhľadávanie.

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');

Výstup 
true
Vytvoriť kvíz