Search a value in a special 2D Sorted Matrix

[Question]
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.

[Analysis]

Binary search will work on this question. The 2nd condition is a key to apply Binary Search on this 2D sorted matrix. One way is to treat the 2D array as 1D array and do a Binary Search. Another way is to do Binary Search on all first elements of each row; then do a binary search on the potential row. The time complexities of two approaches are the same: O(lgMN) == O(lgN+lgM).

[Solution]
class Solution {
public:
    bool searchVector( vector<int> &v, int target ) {
        if (v.size()==0) return false;
        if (v.size()==1) return (v[0]==target);
       
        int mid = v.size()/2;
        if (v[mid]==target) return true;
       
        vector<int> half;
        if (v[mid]<target) {
            half = vector<int>(v.begin()+mid, v.end());
        } else {
            half = vector<int>(v.begin(), v.begin()+mid);
        }
        return searchVector( half, target );
    }
   
    bool searchMatrix(vector<vector<int> > &matrix, int target) {
        if (matrix.size()==0) return false;
        if (matrix.size()==1) return searchVector( matrix[0], target);
       
        int mid = matrix.size()/2;
       
        if (matrix[mid][0]== target) return true;
       
        vector<vector<int>> half;
        if (matrix[mid][0]<target) {
            half = vector<vector<int>> (matrix.begin()+mid, matrix.end());
        } else {
            half = vector<vector<int>> (matrix.begin(), matrix.begin()+mid);
        }
        return searchMatrix( half, target );
    }
};