Searching a 2D Sorted Matrix Part II | LeetCode

Write an efficient algorithm that searches for a value in an n x m table (two-dimensional array). This table is sorted along the rows and columns — that is,
Table[i][j] ≤ Table[i][j + 1],
Table[i][j] ≤ Table[i + 1][j]

Step-wise Linear Search:
We call this the Step-wise Linear Search method. Similar to Diagonal Binary Search, we begin with the upper right corner (or the bottom left corner). Instead of traversing diagonally each step, we traverse one step to the left or bottom. 

Java code from EPI
  public static boolean matrixSearch(List<List<Integer>> A, int x) {
    int r = 0, c = A.get(0).size() - 1;
    while (r < A.size() && c >= 0) {
      if (A.get(r).get(c).equals(x)) {
        return true;
      } else if (A.get(r).get(c) < x) {
        ++r;
      } else { // A.get(r).get(c) > x.
        --c;
      }
    }
    return false;

  }
Quad Partition:

T(n)  = 3lg n ( T(1) + c ) - c/2 
       = O(3lg n) 
       = O(nlg 3)           <== 3lg n = nlg 3 
       = O(n1.58)

bool quadPart(int mat[][N_MAX], int M, int N, int target, int l, int u, int r, int d, int &targetRow, int &targetCol) {

  if (l > r || u > d) return false;

  if (target < mat[u][l] || target > mat[d][r]) return false;

  int col = l + (r-l)/2;

  int row = u + (d-u)/2;

  if (mat[row][col] == target) {

    targetRow = row;

    targetCol = col;

    return true;

  } else if (l == r && u == d) {

    return false;

  }

  if (mat[row][col] > target) {

    return quadPart(mat, M, N, target, col+1, u, r, row, targetRow, targetCol) ||

           quadPart(mat, M, N, target, l, row+1, col, d, targetRow, targetCol) ||

           quadPart(mat, M, N, target, l, u, col, row, targetRow, targetCol);

  } else {

    return quadPart(mat, M, N, target, col+1, u, r, row, targetRow, targetCol) ||

           quadPart(mat, M, N, target, l, row+1, col, d, targetRow, targetCol) ||

           quadPart(mat, M, N, target, col+1, row+1, r, d, targetRow, targetCol);

  }

}

 

bool quadPart(int mat[][N_MAX], int N, int target, int &row, int &col) {

  return quadPart(mat, N, N, target, 0, 0, N-1, N-1, row, col);

}

Improved Binary Partition: 

 T(n) = 2T(n/2) + c lg n
                       lg n
      = 2 lg n T(1) + c ∑ ( 2 lg (n/2k) ) 
                       k=1
      = O(n) + c (2n - lg n - 2)
      = O(n)

bool binPart(int mat[][N_MAX], int M, int N, int target, int l, int u, int r, int d, int &targetRow, int &targetCol) {

  if (l > r || u > d) return false;

  if (target < mat[u][l] || target > mat[d][r]) return false;

  int mid = l + (r-l)/2;

  int row = u;

  while (row <= d && mat[row][mid] <= target) {

    if (mat[row][mid] == target) {

      targetRow = row;

      targetCol = mid;

      return true;

    }

    row++;

  }

  return binPart(mat, M, N, target, mid+1, u, r, row-1, targetRow, targetCol) ||

         binPart(mat, M, N, target, l, row, mid-1, d, targetRow, targetCol);

}

 

bool binPart(int mat[][N_MAX], int N, int target, int &row, int &col) {

  return binPart(mat, N, N, target, 0, 0, N-1, N-1, row, col);

}

Also check
http://leetcode.com/2010/10/searching-2d-sorted-matrix.html
http://leetcode.com/2010/10/searching-2d-sorted-matrix-part-iii.html
Read full article from Searching a 2D Sorted Matrix Part II | LeetCode