題目描述
在一個二維數(shù)組中膛堤，每一行都按照從左到右遞增的順序排序垮媒，每一列都按照從上到下遞增的順序排序倔韭。請完成一個函數(shù)恳谎，輸入這樣的一個二維數(shù)組和一個整數(shù)芝此，判斷數(shù)組中是否含有該整數(shù)憋肖。
輸入輸出分析
每當(dāng)拿到一個算法題的時候，不要腦子中稍微有點(diǎn)思路后婚苹，就開始寫代碼岸更。而是先把題目中規(guī)定的參數(shù)搞清楚，然后把參數(shù)的例子寫出來膊升。
本題兩個參數(shù)舉例：
- 遞增二維數(shù)組
1 2 8 9
2 4 9 12
4 7 10 13
6 8 11 15
注意 題目只說每一行是遞增的怎炊，沒有說增幅是多少，不要以為增幅是1廓译。同時也沒有說行數(shù)和列數(shù)相等
- 要查找的整數(shù)
比如：7评肆、5、0非区、16
對應(yīng)的輸出結(jié)果：true瓜挽、false、false征绸、false
實(shí)現(xiàn)思路
- 暴力遍歷法
面試官要的肯定不是這個結(jié)果久橙，直接跳過
- 二分查找法
仔細(xì)看這個二維數(shù)組最右上角這個數(shù)。它所在的行管怠，左面的數(shù)字比它邢浴；所在的列排惨，下面的數(shù)字比它大：
如果要查詢的數(shù)字比9大吭敢，那么9所在的行就不用在比較了，接下來只需要比較9下面的所有行
如果要查詢的數(shù)字比9小暮芭，那么9所在的列就不用在比較了，接下來只需要比較9左面的所有列
通過這一次的比較欲低，我們就能得到一個新的范圍（矩形）辕宏。接著繼續(xù)利用新范圍右上角的數(shù)字，與要查找的整數(shù)進(jìn)行比較砾莱。比較過后瑞筐，又能得到一個新的進(jìn)一步縮小的范圍（矩形）。如此往復(fù)腊瑟，直到找到目標(biāo)整數(shù)聚假，或者沒有找到。
每一次比較的過程闰非，比較類似二分查找
比如要查找數(shù)字7膘格，那么查找的路徑如下圖：
每一步都是通過比較所在行左面數(shù)字和所在列下面數(shù)字的大小，確定下一步指針的移動方向财松。
同理瘪贱，我們還可以從矩形的左下角的數(shù)字開始比較
最后纱控，別忘了要把特殊情況考慮進(jìn)去，比如參數(shù)的特殊值
代碼實(shí)現(xiàn)
function find(target, array) {
let rows = 0; // 右上角數(shù)字所在的行
let cols = array[0].length - 1; // 右上角數(shù)字所在的列
let result = false;
// 特殊情況判斷. 其他特殊情況比如target不在array里,這里不在列舉
if(array.length === 0) return false;
while(cols >= 0 && rows < array.length) {
if(array[rows][cols] === target) {
result = true;
break;
} else if(array[rows][cols] > target) {
// 如果右上角數(shù)字比目標(biāo)數(shù)字大,向左移動指針
cols--;
} else {
// 如果右上角數(shù)字比目標(biāo)數(shù)字小,向下移動指針
rows++;
}
}
return result;
}
