2 Oct 2013

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);
 }
}

No comments:

Post a Comment