题目概述

给一个二维数组（例如下图），在二维数组的每一列，每一行中，元素的大小是递增的；如何快速判断一个数存不存在

解题思路

这里呢，从右上角开始判断，6的下标（0,2）

有四种情况

1、就是要查找的元素，则返回TRUE

2、比要查找元素大，则x坐标+1，缩小判断的范围

3、比要查找元素小，则y坐标-1，缩小判断的范围

4、范围内不包括任何元素，则表示没有找到，范围FALSE

图解

递归实现

//剑指第三题 //题目：一个M*N数组 //数组从上到下，从左到右为分别为增序 //给一个数，如何快速判断其存不存在 #include<iostream> using namespace std; #include<assert.h> const int M = 3; const int N = 3; //递归实现 //缺点，可能导致栈溢出 bool IsExist(const int* martix, int x, int y, int key) { assert(martix); if (x < M && x >= 0 && y < N && y >= 0) { int num = martix[x*M + y]; if (num > key) return IsExist(martix, x, y - 1, key); else if (num < key) return IsExist(martix, x + 1, y, key); else return true; } return false; }

非递归实现

//剑指第三题 //题目：一个M*N数组 //数组从上到下，从左到右为分别为增序 //给一个数，如何快速判断其存不存在 #include<iostream> using namespace std; #include<assert.h> const int M = 3; const int N = 3; //非递归进行实现 bool IsExistNonR(const int* martix, int x, int y, int key) { assert(martix); while (x < M && x >= 0 && y < N && y >= 0) { int num = martix[x*M + y]; if (num > key) y--; else if (num < key) x++; else return true; } return false; }

测试函数

void TestFindNum() { const int martix[] = { 1, 4, 6, 2, 5, 7, 3, 6, 9 }; int num = 0; cout << "请输入要查找的数:"; cin >> num; cout << "IsExist:" << IsExist(martix, 0, M - 1, num) << endl; cout << "IsExist:" << IsExistNonR(martix, 0, M - 1, num) << endl; }