【剑指Offer】二维数组中的查找

题目描述

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

算法分析

我们可以观察二维数组（m，n）中的4个顶点。

左上角（0，0），向右和向下都是递增。右下角（m，n），向左和向上都是递增，所以我们无法确认哪一个方向能更快找到目标值。

考虑左下角（m，0），向右是递增的，向上的递减的，所以通过比较 target 和 current value 大小，我们可以判断其所在的相对方向。同理右上角。

代码实现

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        int row = array.size();
        int col = array[0].size();
        
        int i, j;
        // 起始点在左下角
        for(i = row - 1, j = 0; i >= 0 && j < col;) {
            if(target == array[i][j])
                return true;
            if(target < array[i][j]){
                i--;
                continue;
            }
            if(target > array[i][j]){
                j++;
                continue;
            }
        }
        
        // 或者起始点在右上角
//    for(i = 0, j = col - 1; i < row && j >= 0;) {
//        if(target == array[i][j])
//            return true;
//        if(target < array[i][j]){
//            j--;
//            continue;
//        }
//        if(target > array[i][j]){
//
//            i++;
//            continue;
//        }
//    }
        
        return false;
    }

};