Search a 2D Matrix

描述

Write an efficient algorithm that searches for a value in an m × 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. [
  2.   [1,   3,  5,  7],
  3.   [10, 11, 16, 20],
  4.   [23, 30, 34, 50]
  5. ]

Given target = 3, return true.

分析

二分查找。

代码

  1. // Search a 2D Matrix
  2. // 时间复杂度O(logn)，空间复杂度O(1)
  3. class Solution {
  4. public:
  5.     bool searchMatrix(const vector<vector<int>>& matrix, int target) {
  6.         if (matrix.empty()) return false;
  7.         const size_t  m = matrix.size();
  8.         const size_t n = matrix.front().size();
  10.         int first = 0;
  11.         int last = m * n;
  13.         while (first < last) {
  14.             int mid = first + (last - first) / 2;
  15.             int value = matrix[mid / n][mid % n];
  17.             if (value == target)
  18.                 return true;
  19.             else if (value < target)
  20.                 first = mid + 1;
  21.             else
  22.                 last = mid;
  23.         }
  25.         return false;
  26.     }
  27. };

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/cpp/search/search-a-2d-matrix.html