目录
题目内容：
思路：
图形演示：
复杂度分析
C源码：
/** *************************************************************************** ******************** ********************* ******************** COPYRIGHT INFORMATION ********************* ******************** ********************* *************************************************************************** ** _oo8oo_ ** o8888888o ** 88" . "88 ** (| -_- |) ** 0\ = /0 ** ___/'==='\___ ** .' \\| |// '. ** / \\||| : |||// \ ** / _||||| -:- |||||_ \ ** | | \\\ - /// | | ** | \_| ''\---/'' |_/ | ** \ .-\__ '-' __/-. / ** ___'. .' /--.--\ '. .'___ ** ."" '< '.___\_<|>_/___.' >' "". ** | | : `- \`.:`\ _ /`:.`/ -` : | | ** \ \ `-. \_ __\ /__ _/ .-` / / ** =====`-.____`.___ \_____/ ___.`____.-`===== ** `=---=` ** *************************************************************************** ******************** ********************* ******************** ********************* ******************** 佛祖保佑 永远无BUG ********************* ******************** ********************* ***************************************************************************/
整形二维数组内元素查找，简称“杨氏矩阵”，是《剑指offer》上的一道经典的题目。
在之前的一篇文章中，我提出了一共三种解决问题的方法，分别是：
遍历，二分查找，第三种并不成熟（也就是充分利用二分查找），为了纠正方法三，于是有了这篇文章。
题目内容：
有一个数字矩阵，矩阵的每行从左到右是递增的，矩阵从上到下是递增的，请编写程序在这样的矩阵中查找某个数字是否存在。
要求：时间复杂度小于O(N);
思路：
假设要找的元素为 7， 设为 key；
我们观察到数组的每一行从左到右递增，每一列从上到下递增：
经过仔细分析：
我们可以试着找到思路：
也就是说，我们把 未查找区域的右上角元素（记为a）与key比较；（意味着我们将从 row = 0，col = j -1 为初始值，然后开始判断）
（记行为i，列为j）
三种可能：
a等于key——这是最简单也是最理想的情况，key就是最右上角元素，找到 于是返回 1 ；
a大于key——由于每一列从上到下递增，a大于key说明最右边的一列都大于key，于是最右侧的一列抛弃，j--；
a小于key——由于每一行从左到右递增，a小于key说明a的左边没有大于key的元素，于是第一行抛弃，i++；
接下来，得到的仍然是矩阵，于是仍然可以用上述操作再次进行操作；但是需要对行 与 列 进行限制——row <= 最大行号，col >= 0;（根据 列号j-- ,但是不能小于0，行号 i++，但是不能越界访问 确定）
图形演示：
（红色框内代表舍弃）
初始状态：
第一次比较：
第二次比较：
第三次比较：
第四次比较：
第五次比较：
复杂度分析
仅仅5次，就找到了key，其实，可以猜测，当矩阵为n阶方阵时，最坏需要比较（n-1）*2 次，才能得到结果——key在最左下角；或者key不存在。
最坏的时间复杂度等于O(N),在一般情况下时间复杂度小于O（N），满足要求。
C源码：
#include<stdio.h>
int Find_int(int arr[][4],int x,int y,int key)
{int i = 0;int j = y-1;//保证坐标的合法性while(i <= x && j >= 0){if( key==arr[i][j] ){return 1;//找到了}else if(arr[i][j] > key){j--;}else if(arr[i][j] < key){i++;}}return 0;//没有找到
}int main()
{int key = 0;scanf("%d",&key);int col = 4,row = 4;int arr[][4] = {{1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15}};int ret = Find_int(arr,row,col,key);printf("%d",ret);return 0;
}完~
转载请注明出处
