74. Search a 2D Matrix

Binary search for candidate row first and binary search in that row.

1:  class Solution {  
2:  public:  
3:    bool searchMatrix(vector<vector<int>>& matrix, int target) {  
4:      int rows = matrix.size(), cols = matrix[0].size();  
5:      int row = 0, col = 0;  
6:      int lo = 0, hi = rows-1;  
7:      while (lo <= hi) {  
8:        int mid = lo + (hi - lo) / 2;  
9:        if (target == matrix[mid][0]) return true;  
10:        else if (target > matrix[mid][0]) {  
11:          lo = mid + 1;  
12:        } else {  
13:          hi = mid - 1;  
14:        }  
15:      }  
16:      if (lo == 0) return false;  
17:      row = lo-1;  
18:      lo = 0; hi = cols-1;  
19:      while (lo <= hi) {  
20:        int mid = lo + (hi - lo) / 2;  
21:        if (target == matrix[row][mid]) return true;  
22:        else if (target > matrix[row][mid]) {  
23:          lo = mid + 1;  
24:        } else {  
25:          hi = mid - 1;  
26:        }  
27:      }  
28:      return false;  
29:    }  
30:  };