DS二分查找_搜索二维矩阵（纯二分查找写法）

本题我写了两个方法，一个是的时间复杂度,就是本文章
一个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)

感谢观看，有任何问题或者文章哪里有问题都可以提出来，我会看滴！！！