二維“有序”數組查找問題的解決| 題目：在一個二維數組中，每一行都按照從左到右遞增的順序排序，誒一列都按照從上到下遞增的順序排序，請完成一個函數，輸入這樣的一個二維數組和一個整數，判斷數組中是否包含了該整數。 |
例如下面的二維數組就是每行、沒列都遞增排序。如果在這個數組中查找數字7，則返回true（找得到）；如果查找數字5，由于數組不含該數字，則返回false。 如下圖所示，會出現三種情況。- 數組中選取的數字（圖中全黑的位置）剛好是要查找的數字（相等），查找過程結束；
- 選取的數字小于要查找的數字，那么根據數組排序的規則，要查找的數字應該在當前位置的右邊或者下邊（如下圖2.1（a）所示）
- 選取的數字大于要查找的數字，那么要查找的數字應該在當前選取的位置的上邊或者左邊。
分析： 由上圖可知，當不等于要查找的數字的時候會出現兩片要查找的區域重疊的情況。我們該怎么考慮呢？ 我們可以從數組的一個角上選取數字來和要查找的數字做比較，情況會變得簡單一些。如：首先選取數組右上角的數字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不在數組中 }結果:
truefalse
