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:
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(vector>& matrix, int target) { //二分查找,將矩陣查找轉化成線性查找 int m = matrix.size(); if(m==0){ return false; } int n = matrix[0].size(); if(n==0){ return false; } int start = 0, end = m*n-1; while(start<=end){ int middle = (start + end)/2; int x = middle / n; int y = middle % n; if(matrix[x][y]==target){ return true; }else if(matrix[x][y]