logo

TechCodeview

Rechercher un élément dans une matrice triée

Étant donné une matrice triée avec[][] de taille n × m et un entier x déterminer si x est présent dans la matrice.
La matrice est triée de la manière suivante :

  • Chaque ligne est triée par ordre croissant.
  • Le premier élément de chaque ligne est supérieur ou égal au dernier élément de la ligne précédente
    (c'est-à-dire mat[i][0] ≥ mat[i−1][m−1] pour tout 1 ≤ i< n).

Exemples :

Saisir: x = 14 tapis[][] = [[ 1 5 9]
[14 20 21]
[30 34 43]]
Sortir: vrai
Explication: La valeur14est présent dans la deuxième ligne, première colonne de la matrice.



Saisir: x = 42 tapis[][] = [[ 1 5 9 11]
[14 20 21 26]
[30 34 43 50]]
Sortir: FAUX
Explication: La valeur42n'apparaît pas dans la matrice.

Table des matières

[Approche naïve] Comparaison avec tous les éléments – O(n × m) Temps et O(1) Espace

L'idée est de parcourir toute la matrice mat[][] et de comparer chaque élément avec x. Si un élément correspond au x, nous retournerons vrai. Sinon à la fin du parcours nous retournerons 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');

Sortir 
true

[Meilleure approche] Utiliser la recherche binaire deux fois - O (log n + log m) Temps et O (1) Espace

Nous localisons d’abord la ligne où la cible x pourrait se trouver en utilisant la recherche binaire, puis nous appliquons à nouveau la recherche binaire dans cette ligne. Pour trouver la bonne ligne, nous effectuons une recherche binaire sur les premiers éléments de la ligne du milieu.

Implémentations étape par étape :

=> Commencez par low = 0 et high = n - 1.
=> Si x est plus petit que le premier élément de la ligne du milieu (a[mid][0]) alors x sera plus petit que tous les éléments des lignes >= mid donc mettez à jour high = mid - 1.
=> Si x est supérieur au premier élément de la ligne du milieu (a[mid][0]) alors x sera supérieur à tous les éléments des lignes< mid so store the current mid row and update low = mid + 1.

Une fois que nous avons trouvé la bonne ligne, nous pouvons appliquer une recherche binaire dans cette ligne pour rechercher l'élément cible 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');

Sortir 
true

[Approche attendue] Utilisation de la recherche binaire une fois - O (log (n × m)) et O (1) Space

L'idée est de considérer la matrice donnée comme un tableau 1D et d'appliquer une seule recherche binaire.
Par exemple, pour une matrice de taille n x m et nous pouvons la considérer comme un tableau 1D de taille n*m ​​alors le premier index serait 0 et le dernier index serait n*m-1. Nous devons donc effectuer une recherche binaire de low = 0 à high = (n*m-1).

Comment trouver l'élément dans la matrice 2D correspondant à index = mid ?

Puisque chaque ligne de mat[][] aura m éléments afin que nous puissions trouver le rangée de l'élément comme (milieu / m) et le colonne de l'élément comme (moyen % m) . Ensuite, nous pouvons comparer x avec arr[mid/m][mid%m] pour chaque mid et compléter notre recherche binaire.

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

Sortir 
true
Créer un quiz