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.
思路：因为题目的条件是第x+1行的第一个数比第x行最后一个数大，所以能够使用二分查找；假设题目条件仅仅说逐行递增，逐列递增，能够从右上角開始查找。此方法也适用于本题。
代码一：
class Solution { public: bool searchMatrix(vector<vector<int> > &matrix, int target) { const int m = matrix.size(); if(m == 0) return false; const int n = matrix[0].size(); if(n == 0) return false; int first = 0; int last = m * n - 1; while(first <= last) { int middle = (first + last) / 2; int val = matrix[middle / n][middle % n]; if(val == target) return true; else if(val < target) first = middle + 1; else last = middle - 1; } return false; } }; 代码二：
class Solution { public: bool searchMatrix(vector<vector<int> > &matrix, int target) { const int m = matrix.size(); if(m == 0) return false; const int n = matrix[0].size(); if(n == 0) return false; int row = 0; int column = n - 1; while(row < m && column >= 0) { if(matrix[row][column] == target) return true; else if(matrix[row][column] > target) column--; else row++; } return false; } };
版权声明：本文博主原创文章。博客，未经同意不得转载。
转载于:https://www.cnblogs.com/bhlsheji/p/4799905.html
相关资源：数据结构—成绩单生成器