Search element in a sorted matrix in C++

In this tutorial, we will learn how to search an element in a sorted matrix in C++. In the first place, we will have a sorted array and a number, and we have to search element.

Simple solution – We will search one by one. The time complexity of searching is O(n^2).
A better solution- The time complexity of this solution is O(n).
Follow these steps :
let x is the number, that we want to find in the matrix.
let nu is the current number that we are dealing with in the array.

• We will start processing from the top right element in the matrix.
• We will compare this element n with the number x.
• If nu=x then return the index position of the matrix. Hence we found the element.
• If nu>x then go left to check the element which is smaller than nu.
• else: go below to check element which is larger than nu.
• Repeat the last three steps to find the element in the matrix.
• Then also, if the element is not found, return false.

You may also like:
Print the corner elements of the matrix using C++

Search element in a sorted matrix

Implementation of approach:

#include<iostream>
#include <bits/stdc++.h> 
using namespace std; 

/* Searches the number x in matrix.If the 
number is found, then prints its index position 
and return true,returns false */
int searchnumber(int a[4][4], int nu, int x) 
{ 
  if (nu == 0) 
    return -1; 
  int smallest = a[0][0], largest = a[nu - 1][nu - 1]; 
  if (x < smallest || x > largest) 
    return -1; 
  
  int i = 0, j = nu - 1; 
  while (i < nu && j >= 0) { 
    if (a[i][j] == x) { 
      cout << " Found at "<< i << ", " << j; 
      return 1; 
    } 
    if (a[i][j] > x) 
      j--; 
    else 
      i++; 
  } 
    cout << " not found"; 
  return 0; 
} 
int main() 
{ 
  int a[4][4] = { { 1, 2, 3, 4 }, 
          { 10, 12, 13, 14 }, 
          { 20, 22, 23,24  }, 
          { 30, 32, 33, 34 } }; 
  searchnumber(a, 3, 23); 

  return 0; 
} 

OUTPUT EXPLANATION:

The output of our C++ program is given below:

OUTPUT: Found at 2, 2