題目描述：

· 在一個(gè)二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請(qǐng)完成一個(gè)函數(shù)，輸入這樣的一個(gè)二維數(shù)組和一個(gè)整數(shù)，判斷數(shù)組中是否含有該整數(shù)。

解題思路：

· 采用二分查找法，時(shí)間復(fù)雜度為O(max(m,n))。

· 先將給定的值key與二維數(shù)組右上角的元素比較：若相等，則返回true；若key小于它，則最后一列的元素肯定都大于key，此時(shí)可以刪除掉最后一列；而若key大于它，則第一行的元素肯定都小于key，此時(shí)可以刪除掉第一行，依次向下比較，如果比較到了左下角的元素，還沒(méi)有發(fā)現(xiàn)等于key的，則返回fasle。

二維數(shù)組中的查找

參考代碼

bool Find(int *arr, int rows, int cols, int key)
{
    int row = 0;
    int col = cols - 1;
    if ((arr != NULL) && (rows > 0 && cols > 0))//判斷是否是空數(shù)組
    {
        while (row<rows&&col >= 0)//循環(huán)直到排除完
        {
            if (arr[row*cols + col] == key)//右上角等于key
            {
                return true;
            }
            else if (arr[row*cols + col] > key)
                --col; //右上角>key，剔除一列
            else
                row++;//否則換下一行
    }
        return false;//未找到
}

參考鏈接

【劍指offer】二分查找二維數(shù)組 | 經(jīng)典面試題——二維數(shù)組查找