74. Search a 2D Matrix(二分查找，剑指offer 1)

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.

Example 1:

Input:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 3
Output: true

Example 2:

Input:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 13
Output: false

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& a, int target) {
        int m = a.size();
        if (m==0) return false;
        int n = a[0].size();
        if (n==0) return false;
        //get target in which col
        int lo = 0;
        int hi = m; 
        while(lo<=hi) {
            int mid = lo + (hi - lo) / 2;
            if (mid>=m) break;
            if (target < a[mid][0]) {
                hi = mid - 1;
            } else if (a[mid][0] < target) {
                lo = mid + 1;
            } else  {
                return true;
            }
        }
        std::cout << lo <<std::endl;
        int col = lo-1;
        if (col<0 ||col>m) return false;
        //get target in col
        lo = 0;
        hi = n;
        while(lo<=hi) {
            int mid = lo + (hi - lo) / 2;
            if (mid>=n) break;
            if (target < a[col][mid]) {
                hi = mid - 1;
            } else if (a[col][mid] < target) {
                lo = mid + 1;
            } else  {
                return true;
            }
        }
        return false;
    }
};

 1 class Solution {
 2     public boolean searchMatrix(int[][] a, int target) {
 3         if (a.length<1)
 4             return false;
 5         int i = 0;
 6         int j = a[0].length-1;
 7         while(i<a.length && j>=0){
 8             if(target==a[i][j])
 9                 return true;
10             else if(target>a[i][j])
11                 i++;
12             else
13                 j--;
14         }
15         return false;
16     }
17 }