c实现在二维数组中的查找

题目描述

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

思路分析

从数组的右上角开始，也就是第一行的最后一个元素。如果该元素等于目标元素，那么直接返回。如果该元素大于目标元素，则说明目标元素可能在该元素的左侧。所以直接找该元素左侧的元素。如果该元素小于目标元素，则说明目标元素可能在该元素的下方。所以直接找该元素下方的元素。这样每次找到都可以排除掉一行或者一列，从而提高查找效率。

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;
}

代码说明

定义一个布尔类型的变量found，初始化为false。若二维数组的指针不为空，行数和列数都大于0，则进入循环。使用变量row表示行，初始化为0，使用变量column表示列，初始化为columns - 1。每次判断该元素是否等于目标元素。若等于，将found赋值为true并退出循环。若该元素大于目标元素，则说明目标元素可能在该元素左侧，所以列号减1。若该元素小于目标元素，则说明目标元素可能在该元素下方，所以行号加1。这样不断循环直到找到目标元素或者越界。

算法分析

该算法的时间复杂度为O(n)，空间复杂度为O(1)。因为每次比较都可以排除掉一行或者一列，整个数组最多比较n次。所以时间复杂度为O(n)。而该算法的空间复杂度为O(1)，因为只使用了少量的变量存储信息。

代码演示

#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;
}

int main()
{
    int matrix[4][4] = {
        {1, 2, 8, 9},
        {2, 4, 9, 12},
        {4, 7, 10, 13},
        {6, 8, 11, 15}
    };
    bool found = Find(&matrix[0][0], 4, 4, 7);
    if(found)
        cout << "Found" << endl;
    else
        cout << "Not found" << endl;
    return 0;
}

输出结果为“Found”，说明找到了目标元素。