LeetCode-Search a 2D Matrix

LeetCode-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.

  解題分析：這道題很簡單，也沒什麼難度，就是一個普通的二分搜索的應用，可能稍微難的地方，就是二維矩陣位置的轉換。

  int  middle = (low + high) / 2;
  if(matrix[middle / n][middle % n] == target)

  對於矩陣位置的轉換采用[middle / n(行的個數)][middle % n]。

  class Solution {
  public:
      bool searchMatrix(vector > &matrix, int target) {
          int m = matrix.size();
          int n = matrix[0].size();
  
          int low = 0;
          int high = m*n-1;
          while(low <= high)
          {
               int  middle = (low + high) / 2;
              if(matrix[middle / n][middle % n] == target)
                  return true;
              else if(matrix[middle / n][middle % n] > target)
                   high = middle -1;
              else if(matrix[middle / n][middle % n] < target)
                   low = middle -1;
          }
          return false;
  
  
      }
  };