# 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

## Leave a Reply