scribe algorithm desc log code ear win gre
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
For example,
Consider the following matrix:
- [
- [1, 3, 5, 7],
- [10, 11, 16, 20],
- [23, 30, 34, 50]
- ]
Given target =3, returntrue.
有序二维矩阵找数,先确定范围再二分查找
- 1 class Solution {
- 2 public: 3 bool searchMatrix(vectorint > >&matrix, int target) {
- 4 int m = matrix.size(),
- n = matrix[0].size();
- 5 int i = 0;
- 6
- for (i = 0; i) {
- 7
- if (target >= matrix[i][0] && target <= matrix[i][n - 1]) 8
- break;
- 9
- }
- 10
- if (i == m) return false;
- 11 int left = 0,
- right = n - 1;
- 12
- while (left <= right) {
- 13 int mid = (left + right) / 2;
- 14
- if (target == matrix[i][left] || target == matrix[i][right] || target == matrix[i][mid]) 15
- return true;
- 16
- if (target < matrix[i][mid]) 17 right = mid - 1;
- 18
- else 19 left = mid + 1;
- 20
- }
- 21
- return false;
- 22
- }
- 23
- };
search-a-2d-matrix——二维矩阵找数
来源: http://www.bubuko.com/infodetail-2154584.html