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.

http://www.lintcode.com/en/problem/search-a-2d-matrix/

Solution

Use binary search twice. Search the first column to find which row the target may locate at, then seach in that row to find the target.

class Solution {
public:
    /**
     * @param matrix, a list of lists of integers
     * @param target, an integer
     * @return a boolean, indicate whether matrix contains target
     */
    bool searchMatrix(vector<vector<int> > &matrix, int target) {
        // write your code here
        int m = matrix.size();
        if(m==0) return false;
        int n = matrix[0].size();
        if(n==0) return false;
        int start = 0; 
        int end = m-1;
        while(start+1<end) {
            int mid = start + (end-start)/2;
            if(matrix[mid][0] < target) {
                start = mid;
            } else if(matrix[mid][0] > target) {
                end = mid;
            } else {
                return true;
            }
        }
        int row = 0;
        if(target < matrix[start][0])
            return false;
        if(target >= matrix[start][0] && target < matrix[end][0]) {
            return iFind(matrix[start], target);
        }
        return iFind(matrix[end], target);
    }

private:
    bool iFind(vector<int> A, int target) {
        int start = 0, end = A.size()-1;
        while (start + 1 < end) {
            int mid = start+(end-start)/2;
            if(target == A[mid]) {
                return true;
            }
            if(target < A[mid]) {
                end = mid;
            } else {
                start = mid;
            }
        }
        if(A[start] == target || A[end] == target) return true;
        return false;
    }
};