|
| 1 | +importjava.util.*; |
| 2 | + |
| 3 | +/** |
| 4 | + * Program to perform Saddleback Search |
| 5 | + * Given a sorted 2D array(elements are sorted across every row and column, assuming ascending order) |
| 6 | + * of size n*m we can search a given element in O(n+m) |
| 7 | + * |
| 8 | + * we start from bottom left corner |
| 9 | + * if the current element is greater than the given element then we move up |
| 10 | + * else we move right |
| 11 | + * Sample Input: |
| 12 | + * 5 5 ->Dimensions |
| 13 | + * -10 -5 -3 4 9 |
| 14 | + * -6 -2 0 5 10 |
| 15 | + * -4 -1 1 6 12 |
| 16 | + * 2 3 7 8 13 |
| 17 | + * 100 120 130 140 150 |
| 18 | + * 140 ->element to be searched |
| 19 | + * output: 4 3 // first value is row, second one is column |
| 20 | + * |
| 21 | + * @author Nishita Aggarwal |
| 22 | + * |
| 23 | + */ |
| 24 | + |
| 25 | +publicclassSaddlebackSearch { |
| 26 | + |
| 27 | +/** |
| 28 | +* This method performs Saddleback Search |
| 29 | +* |
| 30 | + * @param arr The **Sorted** array in which we will search the element. |
| 31 | +* @param crow the current row. |
| 32 | + * @param ccol the current column. |
| 33 | +* @param ele the element that we want to search for. |
| 34 | + * |
| 35 | +* @return The index(row and column) of the element if found. |
| 36 | + * Else returns -1 -1. |
| 37 | + */ |
| 38 | +staticint[]search(intarr[][],intcrow,intccol,intele){ |
| 39 | + |
| 40 | +//array to store the answer row and column |
| 41 | +intans[]={-1,-1}; |
| 42 | +if(crow<0 ||ccol>=arr[crow].length){ |
| 43 | +returnans; |
| 44 | +} |
| 45 | +if(arr[crow][ccol]==ele) |
| 46 | +{ |
| 47 | +ans[0]=crow; |
| 48 | +ans[1]=ccol; |
| 49 | +returnans; |
| 50 | +} |
| 51 | +//if the current element is greater than the given element then we move up |
| 52 | +elseif(arr[crow][ccol]>ele) |
| 53 | +{ |
| 54 | +returnsearch(arr,crow-1,ccol,ele); |
| 55 | +} |
| 56 | +//else we move right |
| 57 | +returnsearch(arr,crow,ccol+1,ele); |
| 58 | +} |
| 59 | + |
| 60 | +/** |
| 61 | + * Main method |
| 62 | + * |
| 63 | + * @param args Command line arguments |
| 64 | + */ |
| 65 | +publicstaticvoidmain(String[]args) { |
| 66 | +// TODO Auto-generated method stub |
| 67 | +Scannersc=newScanner(System.in); |
| 68 | +intarr[][]; |
| 69 | +inti,j,rows=sc.nextInt(),col=sc.nextInt(); |
| 70 | +arr=newint[rows][col]; |
| 71 | +for(i=0;i<rows;i++) |
| 72 | +{ |
| 73 | +for(j=0;j<col;j++){ |
| 74 | +arr[i][j]=sc.nextInt(); |
| 75 | +} |
| 76 | +} |
| 77 | +intele=sc.nextInt(); |
| 78 | +//we start from bottom left corner |
| 79 | +intans[]=search(arr,rows-1,0,ele); |
| 80 | +System.out.println(ans[0]+" "+ans[1]); |
| 81 | +sc.close(); |
| 82 | +} |
| 83 | + |
| 84 | +} |