Tuesday, 20 September 2016

Search in a row wise and column wise sorted matrix

1) Input matrix[n][n] and element e
2) Start with top right element
            i = 0; j= n-1;
3) while termination condition:
            a) if matrix[i][j]==e;
                        Return position
            b) matrix[i][j]<e then move it to down (i++)
            c) matrix[i][j]>e then move it to left (j--).
Repeat a, b and c.

Terminating conditions:
            1. element e found.
            2. i>=row or j<0

public class SearchSortMat {

      private static void findElement(int[][] matrix,int element) {
            int row = matrix.length;
            int i = 0;
            int j = matrix[0].length-1;

            while(i<row && j>=0) {
                  if(element == matrix[i][j]) {
                        System.out.println(element+" found at ("+i+","+j+")");
                        break;
                  } else if(element>matrix[i][j]) {
                        i++;
                  } else {
                        j--;
                  }
            }
            if(i>=row || j<0) {
                  System.out.println(element + " not found !!");
            }
      }

      public static void main(String[] args) {
            int[][] matrix = {{20, 30, 40, 50},
                        {25, 35, 45, 55},
                        {37, 39, 47, 58},
                        {42, 43, 49, 60}};

            int element = 43;

            findElement(matrix, element);
      }
}


Time Complexity: O(n)


No comments:

Post a Comment

Related Posts Plugin for WordPress, Blogger...