剑指offer-JZ1

c++
二维数组中的查找，给定一个traget,一个向量数组，每个向量长度相同，且升序
思路一：
暴力法，遍历判断 O(n*n)=O(n^2)

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        int num=0;
        int row = array.size();
        int col = array[0].size();
        for(int i=0; i<row; i++){
           for (int j=0; j<col; j++)
               if (array[i][j] == target){
                  return true;
               }
        }
        return false;
    }
};

思路二：
因为长度相同，且升序，利用这种规则进行加速：

7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        int num=0;
        int row = array.size();
        int col = array[0].size();
        int i=row-1,j=0;
        while(i>=0 && j<col){
            if (target < array[i][j]){
                i--;
            }else if(target > array[i][j]){
                j++;
            }else{
                return true;
            }
        }
        return false;
    }
};