240. Search a 2D Matrix II

Let i be the row index starting from 0 and j be the column index starting from matrix[0].size()-1.
The invariant is if target is less than matrix[i][j], then it won't be in column j (because elements in column j following row i is larger than the target), so we can move j one backward. Similarly, if target is larger than matrix[i][j], then it won't be in row i, so we can move i one forward.

1:  class Solution {  
2:  public:  
3:    bool searchMatrix(vector<vector<int>>& matrix, int target) {  
4:      int i = 0, j = matrix[0].size() - 1;  
5:      while (i < matrix.size() && j >= 0) {  
6:        if (matrix[i][j] == target) return true;  
7:        else if (matrix[i][j] > target) j--;  
8:        else i++;  
9:      }  
10:      return false;  
11:    }  
12:  };