剑指offer之二维数组中查找

1 问题

二维数组中查找：

在一个二维数组钟，每一行都按照从左到右递增得顺序排列，每一列
都按照从上往下得递增排列，请完成一个函数，输入这样得一个二维数组和一个
整数，判断数组是否含有该整数

列如：

1  2  8   9
2  4  9   12
4  7  10  13
6  8  11  15

2 分析

比如我们要找数字7， 我们先从右上角开始分析，如果要找的值比9小，我们在把列向左移动，然后再去把列向左移动，再去找8，然后发现还是比8小，我们依然向左移动，我们再去找到2，然后发现比2大，我们再把行向下移动，找到4，然后我们发现4还是比7小，我们再把行往下移动，以此类推，然后我们发现找到了7.

3 代码实现

  

   

    

     

    
    

     

      #include <stdio.h>
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int find(int a[][4], int rows, int  columns, int value)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	if (a == NULL || rows <= 0 || columns <= 0)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		return -1;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	int i = 0;
     
    
   

    

     

    
    

     
	int j = columns - 1;
     
    
   

    

     

    
    

     
	while (i < rows 0 && j >= 0)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		if (a[i][j] == value)
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     
			return 0;	
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		else if (a[i][j] > value)
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     
			j--;
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		else 
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     
			i++;
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	return -1;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int find1(int a[][4], int rows, int  columns, int value)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	for (int i = 0; i < rows;)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		for (int j = columns - 1; j >=0;)
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     
			if (a[i][j] == value)
     
    
   

    

     

    
    

     

      			{
     
    
   

    

     

    
    

     
 return 0;	
     
    
   

    

     

    
    

     

      			}
     
    
   

    

     

    
    

     
			else if (a[i][j] > value)
     
    
   

    

     

    
    

     

      			{
     
    
   

    

     

    
    

     
 j--;
     
    
   

    

     

    
    

     

      			}
     
    
   

    

     

    
    

     
			else 
     
    
   

    

     

    
    

     

      			{
     
    
   

    

     

    
    

     
 i++;
     
    
   

    

     

    
    

     

      			}
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	return -1;	
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	int a[4][4] = {{1, 2, 8, 9}, {2, 4, 9 , 12}, {4, 7, 10, 13}, {6, 8, 11, 15}};
     
    
   

    

     

    
    

     
	int result1 = find(a, 4, 4, 11);
     
    
   

    

     

    
    

     
	int result2 = find(a, 4, 4, 3);
     
    
   

    

     

    
    

     
	printf("result1 is %d\n", result1);
     
    
   

    

     

    
    

     
	printf("result2 is %d\n", result2);
     
    
   

    

     

    
    

     
	int result3 = find(a, 4, 4, 11);
     
    
   

    

     

    
    

     
	int result4 = find(a, 4, 4, 3);
     
    
   

    

     

    
    

     
	printf("result3 is %d\n", result3);
     
    
   

    

     

    
    

     
	printf("result4 is %d\n", result4);
     
    
   

    

     

    
    

     
	return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

4 运行结果

  

   

    

     

    
    

     

      result1 is 0
     
    
   

    

     

    
    

     

      result2 is -1
     
    
   

    

     

    
    

     

      result3 is 0
     
    
   

    

     

    
    

     

      result4 is -1
     
    
  
 

5 总结

既然我们分析过程会发现行和列都会变，那么我们肯定需要用2个变量去表示行和列，那么我们肯定要找到便利得终止条件，就是变量行不能大于数组真正得行，然后列的话不能小于0，这个问题我一开始用得2个for，然后for里面写了i和j的变化，后面发现不好理解，然后如果以后我们只要涉及到for里面得i和j更加实际情况需要动态变化的，我们就不要用2个for循环了，我们直接用

while(终止条件) ｛i变化，j变化｝里面改变i和j的值，也就是在while循环里面直接操刀i和j，一定要记住。

文章来源: chenyu.blog.csdn.net，作者：chen.yu，版权归原作者所有，如需转载，请联系作者。

原文链接：chenyu.blog.csdn.net/article/details/86532089