C语言二维数组B[m][n]从做到右，每一行从左至右递增排列，每一列从上至下递增排列的查找方法，时间复杂度为O（m+n）

小咪咪 2022-02-27 23:42 190阅读 0赞

从网上看到的代码，自己实现了一下。  
主要是利用好数组顺序排列这个规律，从右上角开始查找，矩阵是有序的，从右上角来看，向下数字递增，向左数字递减，因此从右上角开始查找：当要查找数字比右上角数字小时，左移；要查找数字比右上角数字大时，下移。同理，也可以从左下角开始查找

#include<stdio.h>
    
     int main(){
     	int y=0; 
     	int m=0,n=0;
     	int a=0,b=0;
     	printf("输入数组行数m:\n");
     	scanf("%d",&m);
     	printf("输入数组列数n:\n");
     	scanf("%d",&n);
     	printf("m，n的值为：%d,%d\n",m,n);
     	int array[m][n];
     	for(int i=0;i<m;i++ ){
     		printf("输入第%d行的%d个数值：\n",i,n);
    	 	for(int j=0;j<n;j++ ){
    	 		scanf("%d",&array[i][j]);
    	 	}
    	 }
    	 printf("输入的数组为：\n");
     	for(int i=0;i<m;i++ ){
     		//printf("输入第%d行的三个数值：\n",i);
    	 	for(int j=0;j<n;j++ ){
    	 		//scanf("%d",&array[i][j]);
    	 		printf("%d\t",array[i][j]);
     			//printf("m，n的值为：%d,%d\n",m,n);
     			//printf("n的值为：%d\n",n);
    	 	}
    	 	printf("\n");
    	 }
    	 int p = 0;//对应m 
    	 int q = n-1;
     	printf("输入要查找的值：\n");
     	scanf("%d",&y);
     	while( p<m && q>=0 ){//这里的判断条件很重要 
     		printf("测试\n");
    	 	if(array[p][q]== y){
    	 		 //a=p;
    	 		 //b=q;
    	 		 printf("在数组中的位置为：[%d][%d]",p,q);
    	 		p++;
    	 		
    	 	}
    	 	if(array[p][q]<y ){
    	 		p++;
    	 	}
    	 	if(array[p][q]>y ){
    	 		q--;
    	 	}
    	 }
    		
     }