題目描述
在一個(gè)二維數(shù)組中（每個(gè)一維數(shù)組的長度相同）爵卒，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序轻姿。請完成一個(gè)函數(shù)臭笆，輸入這樣的一個(gè)二維數(shù)組和一個(gè)整數(shù)，判斷數(shù)組中是否含有該整數(shù)亲澡。
題目分析
如果沒有頭緒的話钦扭，很顯然使用 暴力解法 是完全可以解決該問題的。
即遍歷二維數(shù)組中的每一個(gè)元素床绪，時(shí)間復(fù)雜度：O(n^2)。
其實(shí)到這里我們就可以發(fā)現(xiàn)，使用這種暴力解法并沒有充分利用題目給出的信息癞己。這個(gè)二維數(shù)組是有特點(diǎn)的膀斋。
每一行都是遞增的
每一列都是遞增的
解法
解法一：二分法
對于有序數(shù)組的查找問題而言，二分法是最容易想到的一個(gè)解法痹雅。
在這里仰担，對每一行使用二分查找，時(shí)間復(fù)雜度為 O(nlogn) 绩社。二分查找復(fù)雜度 O(logn)摔蓝，一共 n 行，所以是總體的時(shí)間復(fù)雜度是 O(nlogn) 愉耙。
解法二：規(guī)律法
根據(jù)二維數(shù)組由上到下贮尉，由左到右遞增的規(guī)律。
從左下角開始遍歷朴沿，如果當(dāng)前值比 target 小則往右找猜谚，如果比 target 大則往上找，如果存在赌渣，必然可以找到目標(biāo)數(shù)字魏铅。
即選取右上角或者左下角的元素 a[row] [col] 與 target 進(jìn)行比較， 當(dāng)target小于元素 a[row] [col] 時(shí)坚芜，那么 target 必定在元素 a 所在行的左邊,讓 col-- 览芳；當(dāng) target 大于元素 a[row] [col] 時(shí)，那么 target 必定在元素 a 所在列的下邊,讓 row++ 鸿竖；
代碼如下：
public class Solution {
public boolean Find(int target, int [][] array) {
int row = 0;
int col = array[0].length - 1;
while(row <= array.length - 1 && col >= 0){
if(target == array[row][col])
return true;
else if(target > array[row][col])
row++ ;
else
col-- ;
}
return false;
}
}
解法三：二分規(guī)律法
將解法一和解法二進(jìn)行結(jié)合：對每行每列都使用二分查找路操，此時(shí)的時(shí)間復(fù)雜度為 O(logn * logm)。
比如查找數(shù)字 9千贯，首先使用用二分查找選出一行屯仗，總共有 5 行，那么( 0 + 5 ) / 2 = 2搔谴，所以我們找出了第 2行為基準(zhǔn)行魁袜。
接下來對這一行（即第 2 行）又使用二分查找， 找出這一行（即第 2 行）中最后一個(gè)比目標(biāo)值小的值敦第，這里是 6峰弹。
6 及其所在的行和列把這個(gè)矩形劃分為 4 部分：
左上部分（圖 7 灰色部分），包括所在行的左邊部分和所在列的上邊部分：這一部分是絕對不會(huì)有目標(biāo)數(shù)字的芜果。因?yàn)檫@部分?jǐn)?shù)字肯定比 6 小鞠呈，而 6 又是小于目標(biāo)數(shù)字的，所以左上部分全部小于目標(biāo)數(shù)字右钾。也就是說這個(gè)區(qū)域的數(shù)字不需要再進(jìn)行判斷了蚁吝。
右下部分（圖 7 綠色部分）旱爆，包括所在行的右邊部分，但不包括所在列的下面部分窘茁， 這一部分也是絕對不會(huì)有目標(biāo)數(shù)字的怀伦。因?yàn)檫@部分都比 6 右邊的數(shù)字 11 大，而 11 又比目標(biāo)數(shù)字 9 更大山林，所以右下部分全部都比目標(biāo)數(shù)字大房待。也就是說這個(gè)區(qū)域的數(shù)字也不需要再進(jìn)行判斷了。
左下部分（圖 7 藍(lán)色部分）驼抹，可能含有目標(biāo)數(shù)字桑孩。
右上部分（圖 7 棕色部分），可能含有目標(biāo)數(shù)字框冀。
這樣流椒，實(shí)際上篩選的區(qū)域就只剩下左下部分（圖 7 藍(lán)色部分）和 右上部分（圖 7 棕色部分）這兩塊區(qū)域了，相比于解法二而言左驾，使用這種解法平均情況下每一次查找镣隶，都可以把行和列的長度減少一半。
代碼如下：
public class Solution {
public boolean Find(int target, int [][] array) {
// 特殊情況處理
if (array == null || array.length == 0 || array[0].length == 0) {
return false;
}
?
int h = array.length - 1;
int w = array[0].length - 1;
?
// 如果目標(biāo)值小于最小值 或者 目標(biāo)值大于最大值诡右，那肯定不存在
if (array[0][0] > target || array[h][w] < target) {
return false;
}
return binarySearchIn2DArray(array, target, 0, h, 0, w);
}
public static boolean binarySearchIn2DArray(int[][] array, int target, int startX, int endX, int startY, int endY) {
if (startX > endX || startY > endY) {
return false;
}
//首先安岂，根據(jù)二分法找出中間行
int x = (startX + endX) / 2;
//對該行進(jìn)行二分查找
int result = binarySearch(array[x], target, startY, endY);
//找到的值位于 x 行，result 列
if (array[x][result] == target) {
return true; // 如果找到則成功
}
//對剩余的兩部分分別進(jìn)行遞歸查找
return binarySearchIn2DArray(array, target, startX, x - 1, result + 1, endY)
|| binarySearchIn2DArray(array, target, x + 1, endX, startY, result);
}
?
public static int binarySearch(int[] array, int target, int start, int end) {
int i = (start + end) / 2;
if (array[i] == target || start > end) {
return i;
} else if (array[i] > target) {
return binarySearch(array, target, start, i - 1);
} else {
return binarySearch(array, target, i + 1, end);
}
}
}
