面試題2：二維數組中的查找

查找思路：

首先選取數組中右上角的數字。

（1）如果該數字等於要查找的數字，查詢過程結束；

（2）如果該數字大於要查找的數字，剔除這個數字所在的列；

（3）如果該數字小於要查找的數字，剔除這個數字所在的行。

也就是說，如果要查找的數字不在數組的右上角，則每次都在數組的查找范圍中剔除一行或一列，這樣每一步都可以縮小查找的范圍，直到找到要查找的數字，或者查找范圍為空。

 說明：當然也可以從左下角開始查找，道理一樣；但不能從左上角或右下角開始查找。

上述過程如下圖所示：

C++代碼：

<SPAN style="FONT-SIZE: 18px">#include "stdafx.h"  
#include <assert.h>   
#include <iostream>   
using namespace std;  
  
//在rows行*columns列的二維數組p_nArray中查找nFindNum，找到返回ture, 否則返回false   
bool IsFind(int *p_nArray, int rows, int columns, int nFindNum)  
{  
    assert(p_nArray!=NULL && rows>0 && columns>0);  
  
    if (p_nArray!=NULL && rows>0 && columns>0)  
    {  
        int row = 0;  
        int column = columns - 1;  
  
        while (row<rows && column>=0)  
        {             
            if (*(p_nArray + row*columns + column) == nFindNum)  
            {  
                return true;  
            }  
            else if (*(p_nArray + row*columns + column) > nFindNum)  
            {  
                --column;  
            }  
            else  
            {  
                ++row;  
            }  
        }  
  
        return false;  
    }  
    else  
    {  
       return false;  
    }     
}  
  
int _tmain(int argc, _TCHAR* argv[])  
{  
    int nArr[4][4] = {  
        {1, 2, 8, 9},  
        {2, 4, 9, 12},  
        {4, 7, 10, 13},  
        {6, 8, 11, 15}  
    };    
    cout << IsFind(*nArr, 4, 4, 7) << endl;  
    cout << IsFind(*nArr, 4, 4, 0) << endl;  
    //對於二維數組，行指針加1跳過一行，列指針加1跳過一個元素   
    system("pause");  
    return 0;  
}  
</SPAN>  
#include "stdafx.h"
#include <assert.h>
#include <iostream>
using namespace std;

//在rows行*columns列的二維數組p_nArray中查找nFindNum，找到返回ture, 否則返回false
bool IsFind(int *p_nArray, int rows, int columns, int nFindNum)
{
	assert(p_nArray!=NULL && rows>0 && columns>0);

	if (p_nArray!=NULL && rows>0 && columns>0)
	{
		int row = 0;
		int column = columns - 1;

		while (row<rows && column>=0)
		{			
			if (*(p_nArray + row*columns + column) == nFindNum)
			{
				return true;
			}
			else if (*(p_nArray + row*columns + column) > nFindNum)
			{
				--column;
			}
			else
			{
				++row;
			}
		}

		return false;
	}
	else
	{
	   return false;
	}	
}

int _tmain(int argc, _TCHAR* argv[])
{
	int nArr[4][4] = {
		{1, 2, 8, 9},
		{2, 4, 9, 12},
		{4, 7, 10, 13},
		{6, 8, 11, 15}
	};	
	cout << IsFind(*nArr, 4, 4, 7) << endl;
	cout << IsFind(*nArr, 4, 4, 0) << endl;
	//對於二維數組，行指針加1跳過一行，列指針加1跳過一個元素
	system("pause");
	return 0;
}