LEET code -- Search a 2D Matrix

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

For example,
Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Given target = 3, return true.





可以發現  每一排的最後右邊一定最大
所以可以先搜尋 最右邊 去找要搜尋哪一排

但是我找到那排是用for loop找  會太慢  可以改成binary search

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

class Solution { public: bool searchMatrix(vector<vector<int>>& matrix, int target) { for(int i=0;i<matrix.size();i++){ if(target <=matrix[i][ matrix[i].size()-1 ] ){ for(int j=0;j<matrix[i].size();j++){ if(target == matrix[i][j])return true; } return false; } } return false; } };

-------------
用binary search

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

class Solution { public: bool searchMatrix(vector<vector<int>>& matrix, int target) { for(int i=0;i<matrix.size();i++){ if(target <=matrix[i][ matrix[i].size()-1 ] ){ int start=0,end=matrix[i].size()-1; while(start<=end){ int mid = start +(end-start)/2;//prevent overflow if(matrix[i][mid]==target)return true; if(matrix[i][mid] > target)end=mid-1; else start=mid+1; } return false; } } return false; } };