In each comparison, the goal is to eliminate a row or column until an element is discovered. From the matrix’s upper-right corner, begin your search. Three scenarios could occur:
- Since the pointer is already at the right-most items and the row is sorted, the given number is bigger than the current number, guaranteeing that every element in the current row is smaller than the given number. The entire row is thus removed, and the search for the following row is resumed.
- The current number exceeds the supplied number: This guarantees that every element in the current column exceeds the specified value. Consequently, the entire column is removed, and the search for the prior column—that is, the column on the immediate left—continues.
- The current number and the specified number are equal: The hunt will now be over.
C++
// C++ program to search an element in row-wise
// and column-wise sorted matrix
#include <bits/stdc++.h>
using namespace std;
/* Searches the element x in mat[][]. If the
element is found, then prints its position
and returns true, otherwise prints "not found"
and returns false */
int search(int mat[4][4], int n, int x)
{
if (n == 0)
return -1;
// set indexes for top right element
int i = 0, j = n - 1;
while (i < n && j >= 0) {
if (mat[i][j] == x) {
cout << "Element found at (" << i << ", " << j << ")";
return 1;
}
if (mat[i][j] > x)
j--;
// Check if mat[i][j] < x
else
i++;
}
cout << "Element not found";
return 0;
}
// Driver code
int main()
{
int mat[4][4] = { { 10, 20, 30, 40 },
{ 15, 25, 35, 45 },
{ 27, 29, 37, 48 },
{ 32, 33, 39, 50 } };
// Function call
search(mat, 4, 29);
return 0;
}C
// C program to search an element in row-wise
// and column-wise sorted matrix
#include <stdio.h>
/* Searches the element x in mat[][]. If the
element is found, then prints its position
and returns true, otherwise prints "not found"
and returns false */
int search(int mat[4][4], int n, int x)
{
if (n == 0)
return -1;
// set indexes for top right element
int i = 0, j = n - 1;
while (i < n && j >= 0) {
if (mat[i][j] == x) {
printf("Element found at (%d, %d)", i, j);
return 1;
}
if (mat[i][j] > x)
j--;
else // if mat[i][j] < x
i++;
}
printf("Element not found");
return 0; // if ( i==n || j== -1 )
}
// Driver code
int main()
{
int mat[4][4] = {
{ 10, 20, 30, 40 },
{ 15, 25, 35, 45 },
{ 27, 29, 37, 48 },
{ 32, 33, 39, 50 },
};
// Function call
search(mat, 4, 29);
return 0;
}Java
// JAVA Code for Search in a row wise and
// column wise sorted matrix
class GFG {
/* Searches the element x in mat[][]. If the
element is found, then prints its position
and returns true, otherwise prints "not found"
and returns false */
private static void search(int[][] mat, int n, int x)
{
// set indexes for top right
int i = 0, j = n - 1;
// element
while (i < n && j >= 0) {
if (mat[i][j] == x) {
System.out.print("Element found at (" + i
+ ", " + j + ")");
return;
}
if (mat[i][j] > x)
j--;
else // if mat[i][j] < x
i++;
}
System.out.print("Element not found");
return; // if ( i==n || j== -1 )
}
// Driver code
public static void main(String[] args)
{
int mat[][] = { { 10, 20, 30, 40 },
{ 15, 25, 35, 45 },
{ 27, 29, 37, 48 },
{ 32, 33, 39, 50 } };
// Function call
search(mat, 4, 29);
}
}Python
# Python3 program to search an element
# in row-wise and column-wise sorted matrix
# Searches the element x in mat[][]. If the
# element is found, then prints its position
# and returns true, otherwise prints "not found"
# and returns false
def search(mat, n, x):
i = 0
# set indexes for top right element
j = n - 1
while (i < n and j >= 0):
if (mat[i][j] == x):
print(f"Element found at ({i}, {j})")
return
if (mat[i][j] > x):
j -= 1
# if mat[i][j] < x
else:
i += 1
print("Element not found")
return 0 # if (i == n || j == -1 )
# Driver Code
if __name__ == "__main__":
mat = [[10, 20, 30, 40],
[15, 25, 35, 45],
[27, 29, 37, 48],
[32, 33, 39, 50]]
# Function call
search(mat, 4, 29)C#
// C# Code for Search in a row wise and
// column wise sorted matrix
using System;
class GFG {
/* Searches the element x in mat[][]. If the
element is found, then prints its position
and returns true, otherwise prints "not found"
and returns false */
private static void search(int[, ] mat, int n, int x)
{
// set indexes for top right
// element
int i = 0, j = n - 1;
while (i < n && j >= 0) {
if (mat[i, j] == x) {
Console.Write("Element found at (" + i + ", "
+ j + ")");
return;
}
if (mat[i, j] > x)
j--;
else // if mat[i][j] < x
i++;
}
Console.Write("Element not found");
return; // if ( i==n || j== -1 )
}
// Driver code
public static void Main()
{
int[, ] mat = { { 10, 20, 30, 40 },
{ 15, 25, 35, 45 },
{ 27, 29, 37, 48 },
{ 32, 33, 39, 50 } };
// Function call
search(mat, 4, 29);
}
}JavaScript
// JAVA SCRIPT Code for Search in a row wise and
// column wise sorted matrix
/* Searches the element x in mat[][]. If the
element is found, then prints its position
and returns true, otherwise prints "not found"
and returns false */
function search(mat, n, x) {
// set indexes for top right
let i = 0, j = n - 1;
while (i < n && j >= 0) {
if (mat[i][j] == x) {
console.log("Element found at (" + i + ", " + j + ")");
return;
}
if (mat[i][j] > x)
j--;
else // if mat[i][j] < x
i++;
}
console.log("Element not found");
return; // if ( i==n || j== -1 )
}
// driver program to test above function
let mat = [
[10, 20, 30, 40],
[15, 25, 35, 45],
[27, 29, 37, 48],
[32, 33, 39, 50]
];
search(mat, 4, 29);Output
Element found at (2, 1)