# Given a matrix in which each row and each column is sorted, write a method to find an element in it.

**Problem statement**

Given a matrix in which each row and each column is sorted, write a method to find an element in it.

**Solution**

Assumptions:

1. Rows are sorted left to right in ascending order. Columns are sorted top to bottom in ascending order.

2. Matrix is of size .

This algorithm works by elimination. Every move to the left (–col) eliminates all the elements below the current cell in that column. Likewise, every move down eliminates all the elements to the left of the cell in that row.

**Code**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
public class SearchMatrix { public static boolean search(int arr[][], int x) { int n = arr.length; int m = arr[0].length; int c = m - 1; int r = 0; while (r < n && c >= 0) { if (x == arr[r][c]) { return true; } else { if (x < arr[r][c]) { c--; } else { r++; } } } return false; } public static void main(String[] args) { int[][] arr = { { 1, 2, 3, 4, 5 }, { 11, 12, 13, 14, 15 }, { 21, 22, 23, 24, 25 }, { 31, 32, 33, 34, 35 }, { 41, 42, 43, 44, 45 } }; System.out.println(search(arr, 35)); } } |