?？途W(wǎng)高頻算法題系列-BM18-二維數(shù)組中的查找

題目描述

在一個二維數(shù)組array中（每個一維數(shù)組的長度相同），每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個函數(shù)，輸入這樣的一個二維數(shù)組和一個整數(shù)，判斷數(shù)組中是否含有該整數(shù)。

原題目見：二維數(shù)組中的查找

解法一：二分查找法

因為原二維數(shù)組是嚴(yán)格有序的，即從左到右遞增、從上到下遞增，所以可以采用二分查找的方式進行處理。具體處理過程如下：

• 首先處理特殊場景，當(dāng)數(shù)組為空時，不可能找到目標(biāo)值，直接返回false。

• 否則，從二維數(shù)組的右上角的位置開始，作為二分的中點，x、y分別為二維數(shù)組的坐標(biāo)位置，然后循環(huán)處理直到找到目標(biāo)值：

• 查找終結(jié)的條件就是x、y其中一個走到了二維數(shù)組的邊界之外；

• 如果當(dāng)前位置的值和目標(biāo)值相同，說明找到了目標(biāo)值，返回true；

• 如果當(dāng)前位置的值比目標(biāo)值大，則往左移動，因為左邊的數(shù)更小，然后進行下一輪查找；

• 如果當(dāng)前位置的值比目標(biāo)值小，則往下移動，因為下邊的數(shù)更大，然后進行下一輪查找。

• 最后，如果查找完成沒有找到目標(biāo)值，則返回false。

代碼

1.01^{365} ≈ 37.7834343329 ??

0.99^{365} ≈ 0.02551796445 ??

相信堅持的力量！