74. Search a 2D Matrix

Leetcode link

解题思路

本题给了我们一个二维数组，又告诉我们保证每一行都是升序的，而且下一行的数一定比较大。简单来说，这个就是一个升了一个纬度的升序数组。于是乎，二分法再次成为我们的得力助手。

本题的思路核心在于，如何将二分法计算出来的中间值 mid 对二维数组取值，解决了这一点这题就没什么难度了。

C++

class Solution {
 public:
  bool searchMatrix(vector<vector<int>>& matrix, int target) {
    int m = matrix.size(), n = matrix[0].size();
    int left = 0, right = n * m - 1;
    while (left <= right) {
      int mid = (left + right) / 2;
      // 利用 mid 对二维数组取值
      int value = matrix[mid / n][mid % n];
      if (value == target) return true;
      if (target < value) right = mid - 1;
      if (target > value) left = mid + 1;
    }
    return false;
  }
};

Javascript

var searchMatrix = function(matrix, target) {
    let m = matrix.length, n = matrix[0].length;
    let left = 0, right = n * m - 1;
    while (left <= right) {
      let mid = Math.floor((left + right) / 2);
      // 利用 mid 对二维数组取值
      let value = matrix[Math.floor(mid / n)][mid % n];
      if (value == target) return true;
      if (target < value) right = mid - 1;
      if (target > value) left = mid + 1;
    }
    return false;
};