2021-3-21 240. 搜索二维矩阵 II(二分查找、线性查找)

本文主要是介绍2021-3-21 240. 搜索二维矩阵 II(二分查找、线性查找)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

注：

1.排过序的数组，用二分法

题目：
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

题解：

1.二分法

逐行二分，时间复杂度nlgm
矩阵已经排过序，就需要使用二分法搜索以加快我们的算法。

class Solution {
public:bool binarysearch(vector<vector<int>>& matrix,int target,int i){int left(0);int right(matrix[i].size()-1);while(left<=right){int mid=(left+right)/2;if(matrix[i][mid]<target){left=mid+1;}else if(matrix[i][mid]>target){right=mid-1;}else{return true;}}return false;}bool searchMatrix(vector<vector<int>>& matrix, int target) {int size=matrix.size();for(int i=0;i<size;i++){if(binarysearch(matrix,target,i)==true){return true;} }return false;}
};

2.线性查找

利用矩阵的特征。

从matrix[0][C-1]（最后一列）开始比较，
当target > matrix[i][j]时，增加行。i++;
当target < matrix[i][j]时，减少列。–j。
当target == matrix[i][j]时，找到目标。

寻找的轨迹是个折线。

class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {int size=matrix.size();int row=0,col=matrix[0].size()-1;while(row<size&&col>=0){int value=matrix[row][col];if(target>value){row++;}else if(target<value){col--;}else{return true;}}return false;}
};