面试题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;
}

补充：软件开发 , C++ ,