二维“有序”数组查找问题的解决

﹏ヽ暗。殇╰゛Y 2022-03-28 16:49 174阅读 0赞

<table> 
 <tbody> 
  <tr> 
   <td> 
    <div> 
     <span style="font-size:14px;"><strong>题目</strong>：在一个二维数组中，每一行都按照从左到右递增的顺序排序，诶一列都按照从上到下递增的顺序排序，请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否包含了该整数。</span> 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

例如下面的二维数组就是每行、没列都递增排序。如果在这个数组中查找数字7，则返回true（找得到）；如果查找数字5，由于数组不含该数字，则返回false。

如下图所示，会出现 **三种情况**。

1.  数组中选取的数字（图中全黑的位置）刚好是要查找的数字（**相等**），查找过程结束；
2.  选取的数字**小于**要查找的数字，那么根据数组排序的规则，要查找的数字应该在当前位置的右边或者下边（如下图2.1（a）所示）
3.  选取的数字**大于**要查找的数字，那么要查找的数字应该在当前选取的位置的上边或者左边。

![132014215488866.png][]

**分析：**

由上图可知，当不等于要查找的数字的时候会出现两片要查找的区域重叠的情况。我们该怎么考虑呢？

我们可以 **从数组的一个角上选取数字来和要查找的数字做比较**，情况会变得简单一些。如：首先选取数组右上角的数字9。 **由于9大于7**，并且还是第4列的第一个（也是最小的）的数字，因此7不可能出现在数字9所在的列。于是我们 **把这一列从需要考虑的区域内剔除**，之后只需分析剩下的3列（如下图（a）所示）。在剩下的矩阵中，位于右上角的数字是8，同样 **8大于7**，因此 **8所在的列我们也可以剔除**。接下来我们只要分析剩下的两列即可（如下图（b） 所示）。

在由剩下的两列组成的数组中，数字2位于数字的右上角。 **2小于7**，那么要查找的7可能在2的右边，也有可能在2的下边。在前面的步骤中，我们已经发现2右边的列都已经被剔除了每页就是说7不可能出现在2的右边，因此7只有可能出现在2的下边。于是我们 **把数字2所在的行也剔除**，值分析剩下的三行两列数组（如下图（c)所示）。在剩下的数字中4位于右上角，和前面一样，我们把数字 **4所在的行也剔除**，最后剩下两行两列数字（如图（d）所示）

在剩下的两行两列4个数字中， **位于右上角的刚好就是我们要查找的数字7**，于是 **查找过程**就可以 **结束**了。

注：矩阵中加颜色的的区域是下一步查找的范围。

**总结**

总结上述查找的过程，我们发现如下规律：首先选取数组中右上角的数字。如果该数字 **等于**要查找的数字， **查找**过程 **结束**；如果该数字 **大于**要查找的数字， **剔除**这个数字所在 **列**；如果该数字 **小于**要查找的数字， **剔除**这个数字所在的 **行**。

--------------------

**编码实现**

核心算法:

/**
      * 
      * @param num 被查找的二维数组
      * @param rows 行数
      * @param columns 列数
      * @param number 要查找的数字
      * @return 是否找到要查找的数字（number）
      */
     public static Boolean Find(int num[][],int rows,int columns,int number)
     {
      Boolean found = false;
      int row = 0;
      int column = columns - 1 ;
      
      if( rows > 0 && columns >0)
      {
       while(row < rows && column >= 0)
       {
        if(num[row][column] == number)  //查找到
        {
         found = true;
         break;
        }
        else if(num[row][column] >number)
        {
         --column;  //删除列
        }
        else
        {
         ++row;  //删除行
        }
         
       }
      }
      return found;
     }

**测试：**

public static void main(String[] args)
     {
      //初始化数字的值
      int num[][]= {
         {1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15}};
      
      System.out.println(Find(num,4,4,7)); //在数组中
      
      System.out.println(Find(num,4,4,5)); //5不在数组中
     }

**结果:**

true
    false

[132014215488866.png]: /images/20220328/9e8463c920884f3b987f6f4f4d41b76a.png