Problem:

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:

Since each row of the given matrix is sorted, we can use binary search to accelarate the search.

To locate the which to use binary search, we need to find 2 rows that row1's first element is less than target and row2's first element is greater then target. Then apply binary search to row1.

A problem here is the last row will never be searched, so we need to binary search it at last.

 

Code:

1 class Solution { 2 public: 3     bool searchMatrix(vector
      
       
         > &matrix, int target) { 4         // Start typing your C/C++ solution below 5         // DO NOT write int main() function 6         if (matrix.size() == 0) { 7           return false;   8         } else if (matrix.size() == 1) { 9             return bs(matrix[0], target);10         } else {11             for (int i=1; i
        
          target && matrix[i-1][0] < target)15                     return bs(matrix[i-1], target);16             }17         18             return bs(matrix[matrix.size()-1], target);19         }20     }21     22     bool bs(vector
         
           &array, int target) {23         int lo = 0, hi = array.size()-1;24         25         while (lo <= hi) {26             int mid = (lo+hi) / 2;27             28             if (array[mid] == target) {29                 return true;30             } else if (array[mid] > target) {31                 hi = mid - 1;32             } else {33                 lo = mid + 1;34             }35         }36         37         return false;38     }39 };