0074.cpp (1651B)
1 class Solution { 2 public: 3 bool searchMatrix(vector<vector<int>> &matrix, int target) { 4 int n = matrix.size(), m = matrix[0].size(), row = n - 1; 5 for (int i = 0; i < n - 1; i++) { 6 if (matrix[i + 1][0] > target) { 7 row = i; 8 break; 9 } 10 } 11 12 int low = 0, high = m - 1; 13 while (low <= high) { 14 int mid = low + (high - low) / 2; 15 if (matrix[row][mid] == target) 16 return true; 17 else if (matrix[row][mid] < target) 18 low = mid + 1; 19 else 20 high = mid - 1; 21 } 22 return false; 23 } 24 }; 25 26 // Treat the matrix as a sorted list 27 class Solution { 28 public: 29 bool searchMatrix(vector<vector<int>> &matrix, int target) { 30 int n = matrix.size(), m = matrix[0].size(); 31 int low = 0, high = m * n - 1; 32 while (low <= high) { 33 int mid = low + (high - low) / 2; 34 if (matrix[mid / m][mid % m] == target) return true; 35 if (matrix[mid / m][mid % m] < target) 36 low = mid + 1; 37 else 38 high = mid - 1; 39 } 40 return false; 41 } 42 }; 43 44 // Binary Search Tree 45 class Solution { 46 public: 47 bool searchMatrix(vector<vector<int>> &matrix, int target) { 48 int n = matrix.size(), m = matrix[0].size(); 49 int row = 0, col = m - 1; 50 51 while (row < n && col > -1) { 52 if (matrix[row][col] == target) return true; 53 if (target > matrix[row][col]) 54 row++; 55 else 56 col--; 57 } 58 return false; 59 } 60 };