s4553711
5/18/2017 - 3:37 PM

74.cpp

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.size() == 0) return false;
        int col = matrix[0].size();
        int row = matrix.size();
        
        if (col == 1 && row == 1) {
            return matrix[0][0] == target;
        }
        
        int left = 0;
        int right = col * row - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            int midR = mid / col;
            int midC = mid % col;
            cout << "mid: " << mid << ", l: " << left  << ", r: " << right << endl;
            
            if (left + 1 == right) {
                int L1 = left / col;
                int L2 = left % col;
                int R1 = right / col;
                int R2 = right % col;
             
                if (matrix[L1][L2] == target || matrix[R1][R2] == target) {
                    return true;
                } else {
                    return false;
                }                
            }
            
            if (matrix[midR][midC] == target) {
                return true;
            } else if (matrix[midR][midC] > target) {
                right = mid;
            } else {
                left = mid;
            }
        }
        return false;
    }
};