Searching Algorithms for 2D Arrays (Matrix)

In this article, we will explore three types of matrix search: Unsorted matrices, Completely sorted matrices, and Semi-sorted matrices (sorted row-wise, column-wise, or both).

1. Search in an Unsorted 2D Array

Examples:

Input: mat[][] = [[77, 12, 9],
[4, 1, 5],
[6, 8, 3]]
target = 5
Output: Element found in the matrix
Explanation: We traverse the matrix and find 5 at position (1, 2).

Input: mat[][] = [[1, 5, 9],
[6, 4, 7],
[6, 1, 3]]
target = 10
Output: Element not found in the matrix
Explanation: We check all elements in the matrix, and 10 is not present.

Approach:

Linear Search is the simplest technique for finding an element. In the case of an unsorted 2D matrix, we must traverse each cell one by one to check for the target element. Since there is no ordering of elements, we cannot optimize the search — we simply scan through all rows and columns until the element is found or the entire matrix has been checked.

// C++ program to search an element in an // unsorted 2D Array using Linear Search #include <iostream> #include <vector> using namespace std; // Function to search for the target in matrix bool searchInUnsortedMatrix(vector<vector<int>> &mat,  int target) {  // Traverse all rows  for (int i = 0; i < mat.size(); i++) {  // Traverse all columns  for (int j = 0; j < mat[i].size(); j++) {  // Check if current element matches the target  if (mat[i][j] == target) {  return true;  }  }  }  // Target not found in the matrix  return false; } // Driver code int main() {  vector<vector<int>> mat = {  {7, 2, 9},  {4, 1, 5},  {6, 8, 3}  };  int target = 5;  if (searchInUnsortedMatrix(mat, target)) {  cout << "Element found in the matrix" << endl;  }   else {  cout << "Element not found in the matrix" << endl;  }  return 0; } 

// Java program to search an element in an // unsorted 2D Array using Linear Search class GfG {  // Function to search for the target in matrix  static boolean searchInUnsortedMatrix(int[][] mat, int target) {  // Traverse all rows  for (int i = 0; i < mat.length; i++) {  // Traverse all columns  for (int j = 0; j < mat[i].length; j++) {  // Check if current element matches the target  if (mat[i][j] == target) {  return true;  }  }  }  // Target not found in the matrix  return false;  }  public static void main(String[] args) {  int[][] mat = {  {7, 2, 9},  {4, 1, 5},  {6, 8, 3}  };  int target = 5;  if (searchInUnsortedMatrix(mat, target)) {  System.out.println("Element found in the matrix");  }   else {  System.out.println("Element not found in the matrix");  }  } } 

# Python program to search an element in an # unsorted 2D Array using Linear Search # Function to search for the target in matrix def searchInUnsortedMatrix(mat, target): # Traverse all rows for i in range(len(mat)): # Traverse all columns for j in range(len(mat[i])): # Check if current element matches the target if mat[i][j] == target: return True # Target not found in the matrix return False if __name__ == "__main__": mat = [ [7, 2, 9], [4, 1, 5], [6, 8, 3] ] target = 5 if searchInUnsortedMatrix(mat, target): print("Element found in the matrix") else: print("Element not found in the matrix") 

// C# program to search an element in an // unsorted 2D Array using Linear Search using System; class GfG {  // Function to search for the target in matrix  static bool searchInUnsortedMatrix(int[,] mat, int target) {  // Traverse all rows  for (int i = 0; i < mat.GetLength(0); i++) {  // Traverse all columns  for (int j = 0; j < mat.GetLength(1); j++) {  // Check if current element matches the target  if (mat[i, j] == target) {  return true;  }  }  }  // Target not found in the matrix  return false;  }  static void Main() {  int[,] mat = {  {7, 2, 9},  {4, 1, 5},  {6, 8, 3}  };  int target = 5;  if (searchInUnsortedMatrix(mat, target)) {  Console.WriteLine("Element found in the matrix");  }   else {  Console.WriteLine("Element not found in the matrix");  }  } } 

<script>  // JavaScript code for the above approach  const linearSearch = (arr, target) => {  for (let i = 0; i < arr.length; i++) {  for (let j = 0; j < arr[i].length; j++) {  if (arr[i][j] == target) {  return [i, j];  }  }  }  return [-1, -1];  }  // Driver code   let arr = [[3, 12, 9],  [5, 2, 89],  [90, 45, 22]];  let target = 89;  let ans = linearSearch(arr, target);  document.write(`Element found at index: [${ans[0]} ${ans[1]}]`);  // This code is contributed by rakeshsahni </script> 

Element found in the matrix 

Time Complexity: O(n * m), every cell is visited once.
Space Complexity: O(1), no extra space is used except variables.

2. Search in a Sorted 2D Array

Examples:

Input: mat[][] = [[1, 3, 5],
[7, 9, 11],
[13, 14, 17]]
target = 9
Output: Element found in the matrix
Explanation: Element 9 found at position (1, 1).

Input: mat[][] = [[1, 5, 6],
[7, 8, 10],
[11, 12, 13]]
target = 4
Output: Element not found in the matrix
Explanation: We check all elements in the matrix, and 4 is not present.

Approach:

We call 2D array sorted if every row is individually sorted and all items of a row are smaller than or equal to the next row (if next row exists) In other words, a 2D is called sorted if we write elements of the 2D array (considering standard row major order) as 1D sorted array.

For example, in the below 2D array:

Convert it to 1D array 

Please refer Search in a Sorted 2D Array for different algorithms to search in a 2D array.  

3. Search in a Semi-Sorted 2D Array

There are more versions of searching in a matrix, please refer the below articles.

• Search in 2D array where individual rows are sorted
• Search in 2D array where individual columns are sorted
• Search in a row sorted and column sorted 2D array
• Find median in row wise sorted matrix
• Count zeros in a row wise and column wise sorted matrix