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 603
3
13
16

Output

Copy

true
false
true

题目要求：

搜索num在二维矩阵中是否存在，可以直接遍历全部元素，但是可以依据题目条件；
 

该矩阵有以下特性：

1. 每行中的整数从左到右升序排列；

2. 每行的第一个整数大于前一行的最后一个整数。

所以我们可以直接遍历每一行的第一个元素，判断是否存在这个元素，还有是否在这一行

思路：

1.num与第一列每个元素比较一下判断在第几行
2.遍历第几行看能不能查找到num

样例：

1.

2.

3.

关键代码：

判断数在第几行

判断哪一行是否存在着个数

全部代码：

#include <iostream>
#include <string.h>
using namespace std;
const int maxn = 1e2 + 10;
int shuzu[maxn][maxn];
int main()
{int n, m;while (cin >> n >> m){memset(shuzu, 0, sizeof(shuzu));for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++)///输入矩阵{cin >> shuzu[i][j];}}int t;cin >> t;while (t--){int num;cin >> num;///要查找的数int i = 1;for (i = 1; i <= n; i++){if (num <= shuzu[i][1])///num找到第一个大于他的数他就在那个数的前一行就是i-1行{break;}}if (i == 1)///i=1，说明比第一行最小的数都小，那就不存在这个数{cout << "false" << endl;continue;}int j;for (j = 1; j <= m; j++)///遍历i-1行看看有没有与num相等的数{if (shuzu[i - 1][j] == num){break;///找到就保留退出循环}}///tips：数组我开的比较大，所以j如果没找到会变成m+1，如果开的刚刚好的人会出现越界状况if (shuzu[i - 1][j] == num)///判断是否与num相等，因为也可能没找到。{cout << "true" << endl;}else{cout << "false" << endl;}}}return 0;
}

今天就小小水一下吧！
再见再见再见！！！