Search in a row wise and column wise sorted matrix

Find number in sorted matrix

---

Given an n x n matrix, where every row and column is sorted in increasing order.  Given a number k, how to decide whether this k is in the matrix. OR Search number in a row wise and column wise sorted matrix.

Lets understand the problem statement graphically and it will be more clear,

Algorithm

---

There are many approach to solve this problem, Lets see few of them.

Approach 1: 
Check for the number one by one by looking at each element of the array.
This approach is not efficient as in worst case we need to traverse complete matrix to identify whethet element is present or not.

Approach 2:
As matrix ix sorted, we can apply binary search on each row and identify whether element is present or not.

Approach 3:
In this approach, we will start our search by looking at Right most element of first row.

1. If Current Element =  Search element, Return True, element found.
2. If Current Element <  Search element, It means all element on left of current element are smaller and no need to look on left. Check element on next column.
3. If Current Element >  Search element, It means all element on below current element are higher and no need to look down. Check element in left side on same row.

Lets take an example and understand the solution:

Search in a row wise and column wise sorted matrix Java Program

---

package javabypatel;

public class SearchElementInSortedRowColumnMatrix {
 
 public static void main(String[] args) {
  new SearchElementInSortedRowColumnMatrix();
 }

 public SearchElementInSortedRowColumnMatrix() {
  int[][] arr = {
   {1,   2,  3, 4},
   {5,   6,  7, 8},
   {9,  10, 11, 12},
   {13, 14, 15, 16}
  };

  int toSearch=10;

  int column=arr[0].length-1;
  int row=0;
  boolean isFound=false;

  while(row<arr.length && column>=0){ 
   if(arr[row][column] == toSearch){
    isFound=true;
    break;
    
   }else if(toSearch > arr[row][column]){
    row++;
    
   }else{
    column--;
   } 
  } 
  System.out.println(isFound);
 }
}

You may also like to see

---

Count zeros in a row wise and column wise sorted matrix

Find Largest and Smallest number in Array

Find middle element of a linked list

Union and Intersection of Two Sorted Arrays

Merge two sorted arrays in Java

How is ambiguous overloaded method call resolved in java

Enjoy !!!! 

If you find any issue in post or face any error while implementing, Please comment.