1.2 二维数组查找

1 二维数组的查找

问题描述

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

问题分析

• 与一维查找类似。找到中间数字，每次移动可以舍弃掉一半的数字。由于给定的二维数组具备每行从左到右递增以及每列从上到下递增的特点，当访问到一个元素时，可以排除数组中的部分元素。
• 从二维数组的右上角开始查找。如果当前元素等于目标值，则返回 true。如果当前元素大于目标值，则移到左边一列。如果当前元素小于目标值，则移到下边一行。
• 从二维数组的左下角开始查找。具有完全一致的效果。
  

问题分类

• 线性数据结构
• 枚举法
• 查找问题

策略选择

算法设计

• 若数组为空，返回 false
• 初始化行下标为 0，列下标为二维数组的列数减 1
• 重复下列步骤，直到行下标或列下标超出边界
  • 获得当前下标位置的元素 num
  • 如果 num 和 target 相等，返回 true
  • 如果 num 大于 target，列下标减 1
  • 如果 num 小于 target，行下标加 1
• 循环体执行完毕仍未找到元素等于 target ，说明不存在这样的元素，返回 false`

算法分析

• 时间复杂度O(m+n)
• 空间复杂度O(1)

算法实现

bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
    int i = matrix.size() - 1, j = 0;
    while(i >= 0 && j < matrix[0].size())
    {
        if(matrix[i][j] > target) i--;
        else if(matrix[i][j] < target) j++;
        else return true;
    }
    return false;
}