天天看點

面試題3 ----二維數組中的查找

題目:

        在一個二維數組中,每一行都按照從左到右遞增的順序排序,每一列都按照從上到下遞增的順序排序。請完成一個函數,輸入這樣的一個二維數組和一個整數,判斷數組中是否含有該整數。

面試題3 ----二維數組中的查找
面試題3 ----二維數組中的查找
面試題3 ----二維數組中的查找

在剩下的兩行兩列4個數字中,位于右上角的剛好就是我們要查找的數字7,于是查找過程就可以結束了。

面試題3 ----二維數組中的查找

矩陣的加陰影背景的區域是下一步查找的範圍。代碼如下:

bool Find(int* matrix,int  rows,int columns,int number)

{

bool found = false;

if (matrix != NULL && rows > 0 && columns > 0)

{

int row = 0;

int column = columns - 1;

while (row < rows && column >= 0)

{

if (matrix[row*columns + column] == number)

{

found = true;

break;

}

else if (matrix[row*columns + column] > number)

--column;

else

++row;

}

}

return found;

}

以上是每一次選取數組查找範圍内的右上角數字,也可以選取左下角數字(但是不能選擇左上角或者右下角)。

繼續閱讀