本题我写了两个方法，一个是的时间复杂度,就是本文章
一个m+n时间复杂度，这个比较简单，如果不会二分法可以看这篇文章
Description
使用二分查找法来判断m*n矩阵matrix中是否存在目标值target。
该矩阵有以下特性：
1. 每行中的整数从左到右升序排列；
2. 每行的第一个整数大于前一行的最后一个整数。
Input
第一行输入m和n，分别表示矩阵的行数和列数，接着输入m*n个整数。
接着，输入查找次数t，接着依次输入t个整数target。
Output
对于每次查找，若target存在于矩阵中，则输出true，否则输出false。
共输出t行。
Sample
#0
Input
Copy
3 4 -1 3 5 7 10 11 16 20 23 30 34 60 3 3 13 16
Output
Copy
true false true
思路：
1.矩阵长这样：
2.找到在第几行
我们可以先判断在第几行，只用拿我们要查询的num与第一列的值比较，
如：
-1 10 23 0x3f3f3f
tips：找到第一个比num=11大的数，那这个数所在的前一行就是num可能在的行，设置一个无穷大在末尾就是为了如果在最后一行的话，那他也比第1列就是23的值大如果我们的num=55时，所以设置一个无穷大界限，55遇到无穷大，所以就知道他可能在无穷大的上一行了
3.在所在的行里面找，看是否存在这个数
代码块：
1.初始化，且设置一个无穷大方便查找在第几行
这样子可以方便我们查找在第几行
2.查找在第几行：
3.然后在行里面查找是否有这个值：
tips：有人会问我好像没有处理比第一行第一个数都小的数欸，其实那时候left=0，然后在第0行里面搜了一遍肯定没有这个数，所以无论如何matrix[left][l]都不可能==num，而且我也有试验过了
样例测试:
1.不在矩阵里，比矩阵第一个数都小的
2.在矩阵里的数
3.数的范围在矩阵里但是没有这个数
4.比矩阵最大的数都大的数
3 4
-1 3 5 7
10 11 16 20
23 30 34 60
4
-5
false
11
true
13
false
99
false完整代码：
#include <iostream>
using namespace std;
const int maxn = 1e3 + 10;
int matrix[maxn][maxn];
int main()
{
int m, n;
cin >> m >> n;
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
cin >> matrix[i][j];///初始化矩阵
}
}
matrix[m][0] = 0x3f3f3f;//插入一个无穷大的值在第一列末尾
int t;
cin >> t;
while(t--)
{
int num;
cin >> num;
///用二分法查找在第几行
int left = 0, right = m + 1;
while (left < right - 1)
{
int mid = (left + right) >> 1;
if (matrix[mid][0] > num)//如果比num大就让right=mid因为
{ //此时遇到的比num大的数未必是第一个比num大的
right = mid;
}
else //<=num的直接让left=mid
{
left = mid;
}
}
///可以得出大概在left行里
///求是否在这一行里
int l = 0, r = n;
while (l < r - 1)
{
int mid = (l + r) >> 1;
if (matrix[left][mid] <= num)//这里就是普通二分查找了
{
l = mid;
}
else
{
r = mid;
}
}
if (matrix[left][l] == num)//矩阵里面存在着个数
{
cout << "true" << endl;
}
else//矩阵里面不存在这个数
{
cout << "false" << endl;
}
}
}这个写法是我要做ppt的时候发现好像我之前做的有点没按照要求所以重新做的。有过前台样例和部分后台样例。
原理就是这样的，不知道代码最后会不会有点小瑕疵，这个代码没有提交过有人可以拿去试一下(bushi)
感谢观看，有任何问题或者文章哪里有问题都可以提出来，我会看滴！！！
