Given a row wise and column wise sorted two dimensional array or matrix. How to search for an element efficiently?
Example of the array can be
int[][] matrix = {
{1,3,5,7,9},
{10,12,14,16,18},
{19,21,23,25,27},
{28,30,32,34,36},
{37,39,41,43,45}
};
This can be done using the following algorithm.
We start our search with the top right element.
- If it is equal to the key, we print corresponding indices and we are done!.
- If the key is greater than the current element, we move to the next row because all the elements in the current row prior to this element are lesser.
- If the key is less than the given element, we move to the previous column. The reason is similar to the above.
We continue this search until we find the key or until we confirm the element is not present. If we reach last row first column, we can confirm that the element is not present.
Here is the java implementation of the above algorithm. The time complexity of this program is O(n) and n is the number of rows and columns.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /** | |
| * Created with IntelliJ IDEA. | |
| * User: Ravi | |
| * Date: 10/17/13 | |
| * Time: 6:41 AM | |
| * To change this template use File | Settings | File Templates. | |
| */ | |
| public class SearchSortedMatrix { | |
| public static void main(String [] args) | |
| { | |
| int [][] matrix = { | |
| {1, 3, 4, 6, 9}, | |
| {7, 10, 13, 15, 21}, | |
| {8, 12, 14, 17, 25}, | |
| {15,16, 18, 22, 26}, | |
| {19,20, 23, 24, 30} | |
| }; | |
| matrixFind(matrix, 18); | |
| matrixFind(matrix, 8); | |
| matrixFind(matrix, 7); | |
| matrixFind(matrix, 9); | |
| matrixFind(matrix, 2); | |
| matrixFind(matrix, 20); | |
| matrixFind(matrix, 17); | |
| } | |
| public static void matrixFind(int[][]matrix, int key) | |
| { | |
| //start at the top right corner | |
| int i = 0; //Row index | |
| int j = matrix[0].length - 1;//Column index | |
| while( i < matrix.length && j >= 0 ) | |
| { | |
| if( matrix[i][j] == key ) | |
| { | |
| System.out.println( key + " is found at (" + i + "," + j + ")"); | |
| return; | |
| } | |
| else if( matrix[i][j] > key ) | |
| { | |
| j--;//Move to previous column | |
| } | |
| else | |
| { | |
| i++;//Move to next row | |
| } | |
| } | |
| System.out.println( key + " is not found!"); | |
| } | |
| } |
by