074 - Search a 2D Matrix

Search a 2D Matrix

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

For example,
Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Given target = 3, return true.
Hide Tags
Array Binary Search
Hide Similar Problems
(M) Search a 2D Matrix II


二分查找，先二分行，后二分行内。
当然也可以不递归，还可以行列同时二分。
看到一个更漂亮的解法：
因为数组下一行首比上一行尾大，所以实际上可以看成一个一维数组来进行二分法。

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int sz = matrix.size();
        if(sz)
        {
            int zz = matrix[0].size();
            if(zz)
            {
                if((target<matrix[0][0])||target>matrix[sz-1][zz-1])
                    return false;

                int idx=-1;
                if(false == colSearch(matrix, sz, zz, 0, sz-1, target, idx))
                {
                    //if(-1==idx)
                    //    return false;
                    //else
                        return rowSearch(matrix[idx], 0, zz-1, target);
                }
                return true;
            }
        }
    }
   
    bool colSearch(vector<vector<int>>& mtx, int m, int n,
                      int start, int end, int tgt, int& idx)
    {
        if(start>end)   //should not be here
        {
            idx = -1;
            return false;
        }
        int ms = mtx[start][0];
        int me = mtx[end][0];

        if(tgt==ms) //no need for further searching
        {
            idx = start;
            return true;
        }
        if(tgt==me) //no need for further searching
        {
            idx = end;
            return true;
        }

        if(tgt>me) //in last row
        {
            idx = end;
            return false;
        }
        if((start==(end-1))&&(tgt<me)&&(tgt>ms))    //in other rows
        {
            idx = start;
            return false;
        }
       
        int mid = (start+end)/2;
        if(tgt<mtx[mid][0])
            return colSearch(mtx, m, n, start, mid-1, tgt, idx);
        else
            return colSearch(mtx, m, n, mid, end, tgt, idx);
    }
   
    bool rowSearch(vector<int>& row, int start, int end, int tgt)
    {
        if(start>end)
            return false;

        int ms = row[start];
        int me = row[end];
        if((tgt==ms)||(tgt==me))
            return true;

        if((start==(end-1))&&(tgt<me)&&(tgt>ms))
            return false;

        int mid = (start+end)/2;
        if(row[mid] == tgt)
            return true;

        if(tgt<row[mid])
            return rowSearch(row,start,mid-1,tgt);
        else
            return rowSearch(row,mid+1,end,tgt);
    }
};

12 ms.