LeetCode OJ:Search a 2D Matrix

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.

  算法思想：二分

  class Solution {
  public:
      bool searchMatrix(vector
      
        > &matrix, int target) {
          if(matrix.empty())return false;
          int r=matrix.size();
          int c=matrix[0].size();
          int left=0,right=r*c-1;
          while(left<=right){
              int mid=(left+right)/2;
              if(matrix[mid/c][mid%c]==target)return true;
              if(matrix[mid/c][mid%c]