剑指刷题笔记四：二维数组中的查找

飞熊 • 2023年4月6日下午12:54 • 后端笔记 • 阅读 83

题目：在一个二维数组中，每一行都按照从左到右的顺序依次递增，每一列也按照从上到下的顺序依次递增。请编程完成一个函数，输入一个二维数组和一个整数，判断数组中是否含有该整数。
分析：首先，注意到数组是有序排列的。利用此性质，采用以下算法。首先选取数组中左下角的数字。如果该数字小于要查找的数字，则此列中没有要查找的数字，列数加1；如果该数字大于要查找的数字，则此行中没有要查找的数字，行数减1。如果等于要查找到的数字，则返回结果，查找完成。如果最终在主函数最后返回，则说明找到了右上角，但是没有找到要找的数字，输出查找失败！
此种算法是按照从左下角开始进行搜索的，当然也可以从右上角开始，书上有从右上角开始的代码，思路是相同的。但是注意，不可以从左上角或者右下角开始查找，因为在判断要查找的额整数值和当前位置数组的值的关系之后，行号或者列号缩小范围，产生的效果是等同的，所以无法缩小范围。
以下为测试的二维数组：

// A test matrix
1  2  8  9
2  4  9  12
4  7  10 13
6  8  11 15

以下为实现代码：

#include <iostream>

int main()
{
    const int rows = 4;
    const int columns = 4;
    int matrix[rows][columns] = { {1, 2, 8, 9}, {2, 4, 9, 12}, {4, 7, 10, 13}, {6, 8, 11, 15} };
    int key = 7;// 要查找的值
    int row = rows - 1;//当前的行号
    int column = 0;//当前的列号
    while (row >= 0 && column <= columns - 1) {
        if (matrix[row][column] < key)
            column++;
        else if (matrix[row][column] > key)
            row--;
        else {
            std::cout << "find the wanted number " << key << " ,the place row is " << row + 1 << ","
                << "column is " << column + 1 << std::endl;
            return 1;//查找到，返回
        }
    }
    std::cout << "don't have this number!!!" << std::endl;
    return 0;//未查到，返回
}