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