Edit Question - KnowledgeHub

Title Body

Problem: Given a matrix in which each row and each column is sorted, write a method to find an element in it. It is a classic interview question, here is my solution boolean F(int[][] matrix, int hs, int he, int ws, int we) { if (hs > he || ws > we) return false; int m = (hs + he) / 2; int n = (ws + we) / 2; if (matrix[m][n] == t) { return true; } else if (matrix[m][n] < t) { // find the ele in the same row, right to [m][n] F(m, m, n + 1, we); // find the ele in the same col, upper to [m][n] F(m + 1, he, n, n); // find the ele in the area, where i>m,j>n F(m + 1, he, n + 1, we); } else if (matrix[m][n] > t) { // very similar to previous part } } The running time of the algorithm is log(m) + log(n). I am looking for an algorithm that is more efficient, or with concise code. Having more comments, I come up with following code: // return target recurrence in the matrix int F(int[][] m, int rs, int re, int cs, int ce, int t){ int r1 = rs, r2 = re; int c1 = cs, c2 = ce; int r=0 , c = c1; while( r1 < r2 && c1 < c2 ){ // find the last element that <= t in column c r = FlastLess( r1, r2, c, t) if( r == -1 ) break; else{ // find the first ele in the row that is >=t c = FfirstGreater( r, c1, c2, t); if( c == -1) break; else{ r2 = r; c1 = c; }// else }// else }// while }// f Here is the link to function F1 and F2 Find the first element in a sorted array that is greater than the target void FlastLess(int s, int e, int t){ int l = s, h = e; while( l != h ){ int mid = (l+h)

Tags (comma-separated) Cancel