试题4：二维数组中的查找

题目：

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个 整数，判断数组中是否含有该整数。例如矩阵：

分析：

由于数组已经经过简单排序，所以查找一般不需要完全的遍历。常规的想法是从矩阵的左上角开始搜索，比如查找10这个数字，10比1大，需要继续和1的下方、右方的数字比较，以此类推可以找到10。但是这样从两路开始搜索是有交叉的。一种比较好的方法是从右上角或者左下角开始搜索。每次可以剔除一列或者一行的数据。比如从左下角开始搜索，看左下角的元素是否等于10。搜索目标10比6大（10比该行的最大值都大，第一列中不可能有10），矩阵变为：

再次从8开始搜索，10大于8，（10比该行的最大值都大，第一列不可能有10）矩阵变为：

再次从11开始搜索，10小于11（比该行最小的数字还小，该行不可能有10），矩阵变为：

再次从左下角开始搜索，得到10.
代码实现：

#include <iostream>
using namespace std;
bool Find(int *matrix,int rows,int columns,int number){
    bool found = false;
    if(matrix != nullptr && 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;
}
void test(int *matrix,int rows,int columns,int number){
    if(Find( matrix, rows, columns, number))
        cout<<"查找到目标数字："<<number<<endl;
    else
        cout<<"空指针或者数字不存在"<<endl;

}
int  main(){
    cout<<"测试用例1（空指针）"<<endl;
    test(nullptr,0,0,1);

    cout<<"测试用例2（查找数字为矩阵的最大值）"<<endl;
    int m2[][3] = {{1,2,3},{2,2,5},{3,4,9},{7,8,13}};
    test((int*)m2,4,3,13);

    cout<<"测试用例3（查找数字为矩阵的最小值）"<<endl;
    //int m3[][]={1,2,3;2,2,5;3,4,9;7,8,13};
    test((int*)m2,4,3,1);

    cout<<"测试用例4（查找数字在矩阵的最大和最小值之间）"<<endl;
    test((int*)m2,4,3,4);

    cout<<"测试用例5（查找数字大于矩阵的最大值）"<<endl;
    test((int*)m2,4,3,14);

    cout<<"测试用例6（查找数字小于矩阵的最小值）"<<endl;
    test((int*)m2,4,3,0);
}

注：二维数组在内存中以一维数组的形式存在,所以可以将整型的二维数组强制转换为一维数组使用，这样可以简化二维数组的书写和使用。
int a[][4] = {{1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15}};

int* b = (int*)a ；

下标 = 行号 * 列数 + 列号
如b[5] = b[1 * 4 + 1]