首页 > 代码库 > Leetcode 二分查找 Search a 2D Matrix
Leetcode 二分查找 Search a 2D Matrix
Search a 2D Matrix
Total Accepted: 18506 Total Submissions: 59402My SubmissionsWrite 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.
题意：在一个二维矩阵中找到给定的值。矩阵从上到下从左到右有序
思路：二维空间的二分查找
先在一维里找中间位置，再将该位置转为二维空间里的下标
复杂度：
class Solution {
public:
bool searchMatrix(const vector<vector<int> > &matrix, int target){
if (matrix.empty()) return false;
int m = matrix.size(), n = matrix.front().size();
int begin = 0, end = m * n, middle, row, col;
while(begin < end){
middle = begin + (end - begin) / 2;
int row = middle / n;
int col = middle % n;
if(matrix[row][col] == target) return true;
else if(matrix[row][col] < target) begin = middle + 1;
else end = middle;
}
return false;
}
};Leetcode 二分查找 Search a 2D Matrix
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。