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;
}
};