leetcode

0 class Solution {

1 public:

2 bool searchMatrix(vector<vector<int>> &matrix, int target) {

3 int n = matrix.size(), m = matrix[0].size(), row = n - 1;

4 for (int i = 0; i < n - 1; i++) {

5 if (matrix[i + 1][0] > target) {

6 row = i;

7 break;

8 }

9 }

10

11 int low = 0, high = m - 1;

12 while (low <= high) {

13 int mid = low + (high - low) / 2;

14 if (matrix[row][mid] == target)

15 return true;

16 else if (matrix[row][mid] < target)

17 low = mid + 1;

18 else

19 high = mid - 1;

20 }

21 return false;

22 }

23 };

24

25 // Treat the matrix as a sorted list

26 class Solution {

27 public:

28 bool searchMatrix(vector<vector<int>> &matrix, int target) {

29 int n = matrix.size(), m = matrix[0].size();

30 int low = 0, high = m * n - 1;

31 while (low <= high) {

32 int mid = low + (high - low) / 2;

33 if (matrix[mid / m][mid % m] == target) return true;

34 if (matrix[mid / m][mid % m] < target)

35 low = mid + 1;

36 else

37 high = mid - 1;

38 }

39 return false;

40 }

41 };

42

43 // Binary Search Tree

44 class Solution {

45 public:

46 bool searchMatrix(vector<vector<int>> &matrix, int target) {

47 int n = matrix.size(), m = matrix[0].size();

48 int row = 0, col = m - 1;

49

50 while (row < n && col > -1) {

51 if (matrix[row][col] == target) return true;

52 if (target > matrix[row][col])

53 row++;

54 else

55 col--;

56 }

57 return false;

58 }

59 };