有序二維數組中的查找

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

思路：首先看到這樣一個題目我們先分析題目，把二維數組在紙上畫成一個矩形。列如：1 2 8 9

                                       2 4 9 12  

                                       4 7 10 13     

                                       6 8 11 15

然后從數組中選取一個數字7。分三種情況來分析查找過程：當選取的數字跟要查找的數字相等時，結束。當選取的數字小于要查找的數字時，要查找的數字應該在當前選取數字的右邊或者下邊。當選取的數字大于要查找的數字時，要查找的數字應該在當前選取數字的左邊或者上邊。

這種情況有可能會出現重疊區域，代碼不太容易實現。

我們可以換種角度思考，減少查找的范圍，我們每次都以右上角的數字作為標準進行比較，當查找的數字小于右上角的數字時，剔除該數字所在的這一列。當查找的數字大于右上角的數字時，剔除該數字所在的這一行。慢慢的減少查找的范圍，最終找到該數字。

代碼實現如下：

#include<iostream>
using namespace std;
bool Find(int (*arr)[4],int rows,int cols,int num)
{
	if(arr!=NULL && rows>0 && cols>0)
	{
		int row=0;
		int col=cols-1;
		while(row<rows && col>=0)
		{
			if(arr[row][col]==num)
				return true;
			else if(arr[row][col]>num)
				col--;
			else
				row++;
		}
		return false;
	}
}
int main()
{
	int arr[][4]={1,2,8,9,2,4,9,12,4,7,10,13,6,8,11,15};
	bool ret=Find(arr,4,4,7);
	cout<<ret<<endl;
	return 0;
}