# 行列遞增矩陣的查找 ## 題目描述 在一個m行n列二維數組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個函數，輸入這樣的一個二維數組和一個整數，判斷數組中是否含有該整數。 例如下面的二維數組就是每行、每列都遞增排序。如果在這個數組中查找數字6，則返回true；如果查找數字5，由于數組不含有該數字，則返回false。  ## 分析與解法 ### 解法一、分治法 這種行和列分別遞增的矩陣，有一個專有名詞叫做楊氏矩陣，由劍橋大學數學家楊表在1900年推提出，在這個矩陣中的查找，俗稱楊氏矩陣查找。 以查找數字6為例，因為矩陣的行和列都是遞增的，所以整個矩陣的對角線上的數字也是遞增的，故我們可以在對角線上進行二分查找，如果要找的數是6介于對角線上相鄰的兩個數4、10，可以排除掉左上和右下的兩個矩形，而在左下和右上的兩個矩形繼續遞歸查找，如下圖所示：  ### 解法二、定位法 首先直接定位到最右上角的元素，再配以二分查找，比要找的數（6）大就往左走，比要找數（6）的小就往下走，直到找到要找的數字（6）為止，這個方法的時間復雜度O（m+n）。如下圖所示：  關鍵代碼如下所示： ```c #define ROW 4 #define COL 4 bool YoungMatrix(int array[][COL], int searchKey){ int i = 0, j = COL - 1; int var = array[i][j]; while (true){ if (var == searchKey) return true; else if (var < searchKey && i < ROW - 1) var = array[++i][j]; else if (var > searchKey && j > 0) var = array[i][--j]; else return false; } } ``` ## 舉一反三 1、給定 n×n 的實數矩陣，每行和每列都是遞增的，求這 n^2 個數的中位數。 2、我們已經知道楊氏矩陣的每行的元素從左到右單調遞增，每列的元素從上到下也單調遞增的矩陣。那么，如果給定從1-n這n個數，我們可以構成多少個楊氏矩陣呢？ 例如n = 4的時候，我們可以構成1行4列的矩陣： 1 2 3 4 2個2行2列的矩陣: 1 2 3 4 和 1 3 2 4 還有一個4行1列的矩陣 1 2 3 4 因此輸出4。