剑指 Offer 04. 二维数组中的查找

题目描述

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

题解

从右上角或者左下角看，相当于看一个二叉搜索树。

class Solution { public: bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) { int column = 0, row = matrix.size()-1; while(row>=0 && column<matrix[0].size()){ if(matrix[row][column]>target) --row; else if(matrix[row][column]<target) ++column; else return true; } return false; } };

bug

数组下标越界，主要是因为用到了matrix[0].size()，而matrix.size()可能为0，这样matrix[0]就会出现下标越界。

避免的方法：最简单的是直接在开头加一个判断。也可以在while循环条件中&&的左边保证matrix.size()一定大于0。上面的代码中while(row>=0 && column<matrix[0].size())row初始值就是row = matrix.size()-1，row>=0为真时一定能保证column<matrix[0].size()中的matrix[0]下标不越界。

column<=matrix[0].size()-1和column<matrix[0].size()是不一样的。关键是matrix[0].size()是一个无符号数，如果matrix[0].size()恰好为0，减去1后将执行无符号数减法，得到一个很大的正数，而不是期望中的-1。