https://leetcode.cn/problems/search-a-2d-matrix-ii/submissions/613522892/?envType=study-plan-v2&envId=top-100-liked逻辑法
看到题目第一眼，就想着从左往右，从上往下，只要找到对应的target的范围，以小于大于进行遍历的移动，但在写代码时发现比较难实现，边界情况没有右元素没有下元素，当右元素与下元素相等时等等，实现不太现实而且不一定遍历完全，但冥冥之中又感觉大方向没有问题 ，看了题解后醍醐灌顶，正向思考不太对，为何不反向思考，从右边遍历以排除法来排除元素！
以矩阵左下角与当前位置[x,y]构成矩阵，当[x,y]=target，找到了；当[x,y]<target，则往下走x+1；当[x,y]>target，则往左走，y-1。
//c++
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target)
{
int m=matrix.size(),n=matrix[0].size();
int x=0,y=n-1;
while(x<m&&y>=0)
{
if(matrix[x][y]==target) return true;
if(matrix[x][y]>target) y--;
else x++;
}
return false;
}
};
#python
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
m,n=len(matrix),len(matrix[0])
x,y=0,n-1
while x<m and y>=0:
if matrix[x][y]==target:
return True
if matrix[x][y]>target:
y=y-1
else:
x=x+1
return False常规遍历
不管矩阵有啥规律，直接暴力遍历查找是否有target。
//c++
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target)
{
for(const auto&i:matrix) for(int j:i) if(j==target) return true;
return false;
}
};
#python
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
for i in matrix:
for j in i:
if j==target:
return True
return False二分查找
查找中的二分查找，利用c++与python中的内置函数。
c++
lower_bound是 C++ 标准库中的一个二分查找算法，用于在有序范围内查找第一个>=target的元素。row.begin()和row.end()分别表示当前行的起始和结束迭代器。a是查找结果的迭代器，指向第一个不小于target的元素。
python
bisect.bisect_left是 Python 标准库bisect模块中的一个函数，用于在有序列表中查找目标值的插入位置。i 是当前行的有序列表，
target是要查找的目标值。a是
target在 i 中应该插入的位置索引。如果target存在于 i 中，a是第一个等于target的元素的索引；如果target不存在，a是第一个>=target的元素的索引。
//c++
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target)
{
for(const auto&i:matrix)
{
auto a=lower_bound(i.begin(),i.end(),target);
if(a!=i.end() && *a==target) return true;
}
return false;
}
};
#python
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
for i in matrix:
a=bisect.bisect_left(i,target)
if a<len(i) and i[a]==target:
return True
return False