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.

---

分析：

因为矩阵是行有序并且列有序，查找只需要先按行查找，定位出在哪一行之后再进行列查找即可，所以就是进行两次二分查找。时间复杂度是O(logm+logn)，空间上只需两个辅助变量，因而是O(1)。

代码：

// LeetCode, Search a 2D Matrix // 时间复杂度O(logn)，空间复杂度O(1) class Solution { public: bool searchMatrix(const vector<vector<int>>& matrix, int target) { if (matrix.empty()) return false; const size_t m = matrix.size(); const size_t n = matrix.front().size(); int first = 0; int last = m * n; while (first < last) { int mid = first + (last - first) / 2; int value = matrix[mid / n][mid % n]; if (value == target) return true; else if (value < target) first = mid + 1; else last = mid; } return false; } };