logo

TechCodeview

Vyhledávací prvek v seřazené matici

Vzhledem k seřazené matici spolu s[][] o velikosti n × m a celé číslo x určit, zda je x přítomno v matici.
Matice je tříděna následujícím způsobem:

  • Každý řádek je řazen ve vzestupném pořadí.
  • První prvek každého řádku je větší nebo roven poslednímu prvku předchozího řádku
    (tj. mat[i][0] ≥ mat[i−1][m−1] pro všechna 1 ≤ i< n).

Příklady:

Vstup: x = 14 mat[][] = [[ 1 5 9]
[14 20 21]
[30 34 43]]
výstup: věrný
Vysvětlení: Hodnota14je přítomen ve druhém řádku prvního sloupce matice.



Vstup: x = 42 mat[][] = [[ 1 5 9 11]
[14 20 21 26]
[30 34 43 50]]
výstup: falešný
Vysvětlení: Hodnota42se v matrice neobjevuje.

Obsah

[Naivní přístup] Porovnání se všemi prvky – O(n × m) Čas a O(1) Prostor

Cílem je iterovat celou matrici[][] a porovnat každý prvek s x. Pokud se prvek shoduje s x, vrátíme true. Jinak na konci procházení vrátíme 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ší přístup] Použití binárního vyhledávání dvakrát - O(log n + log m) Čas a O(1) Prostor

Nejprve pomocí binárního vyhledávání najdeme řádek, kde by mohl být cíl x, a poté v tomto řádku znovu použijeme binární vyhledávání. Abychom našli správný řádek, provedeme binární vyhledávání na prvních prvcích prostředního řádku.

Krok za krokem implementace:

=> Začněte s nízkým = 0 a vysokým = n - 1.
=> Pokud je x menší než první prvek prostředního řádku (a[mid][0]), pak x bude menší než všechny prvky v řádcích >= mid, takže aktualizujte high = mid - 1.
=> Pokud je x větší než první prvek prostředního řádku (a[mid][0]), pak x bude větší než všechny prvky v řádcích< mid so store the current mid row and update low = mid + 1.

Jakmile najdeme správný řádek, můžeme použít binární vyhledávání v tomto řádku k vyhledání cílové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čekávaný přístup] Použití binárního vyhledávání jednou - O(log(n × m)) a O(1) prostor

Cílem je považovat danou matici za 1D pole a použít pouze jedno binární vyhledávání.
Například pro matici o velikosti n x m a můžeme ji považovat za 1D pole o velikosti n*m pak první index bude 0 a poslední index n*m-1. Musíme tedy provést binární vyhledávání od low = 0 po high = (n*m-1).

Jak najít prvek ve 2D matici odpovídající indexu = mid?

Protože každá řada mat[][] bude mít m prvků, takže můžeme najít řádek prvku jako (střed / m) a sloupec prvku jako (střed % m) . Pak můžeme porovnat x s arr[mid/m][mid%m] pro každý střed a dokončit naše binární vyhledávání.

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
Vytvořit kvíz