Coding: Search in 2D array

题目描述

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

Solution with iteration:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool Find(vector<vector<int> > array,int target) {
        bool result = false;
        int m = array.size(), n = array[0].size();
        int row = 0, col = n - 1;
        while(row < m && col >= 0){
            if(array[row][col] == target){
                result = true;
                break;
            }
                 
            else if(array[row][col] < target)
                row ++;
            else
                col --;
        }
        return
         
    }
};

Solution with recursion:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    bool Find(vector<vector<int> > array,int target) {
        if(array.size() == 0)
            return false;
        return recursion(array, target, 0, array[0].size() - 1);
    }
    bool recursion(vector<vector<int>> array, int target, int row, int col){
        if(row == array.size() || col == -1)
            return false;
        if(array[row][col] == target)
            return true;
        else if(array[row][col] > target)
            return recursion(array, target, row, col-1);
        else
            return recursion(array, target, row+1, col);
       
        
    }
};