Saddleback Search

Problem Statement: 

Find an element in given matrix , matrix is such that each row and each column is sorted.

Solution:

To Solve this , we start from top right.

1. If element is greater move down

2. If element is lesser move left

3. If the element matches then print row and column indexes

This algorithm is called Saddleback search.
Richard Bird examined this algorithm and incorporated Binary Search in 2006.

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 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44

public class FindNumber { static int[][] matrix= { { 11, 21, 31, 41, 51 }, { 12, 22, 32, 42, 52 }, { 13, 23, 33, 43, 53 } , { 14, 24, 34, 44, 54 }, { 15, 25, 35, 45, 55 } }; public void find(int[][] martix , int num) { int rLen=matrix.length; int cLen=martix[0].length ; int row=cLen-1; int col=0; // Start from top Right while( row >= 0 && col < rLen) { //Move Down if(num > matrix[row][col]) col++; //Move Left else if(num < matrix[row][col]) row--; //Element Found else { System.out.println("Found at : ( "+ row+ " , "+ col + " ) "); return ; } } System.out.println(num + " not found"); } public static void main(String[] args) { FindNumber fnum=new FindNumber(); fnum.find(matrix, 27); } }