二维数组中的查找

1.穷举法(每行单指针)

public:
/*
形如[[1,2],[3,4]]的数组
取其列数，即第一维的size：array[0].size(),
取其行数，即整个array的size：array.size()
然后自array[0][0]遍历
*/
    bool Find(int target, vector<vector<int> > array) {
        int col=array[0].size();//矩阵列数
        int row=array.size();//矩阵行数
        if(!col||!row){return false;}
        else
        {
            for(int i=0;i<row;i++)
            {
                int j=0;
                while(array[i][j]<target)
                {
                    j++;
                }
                if(array[i][j]==target)return true;
                continue;//该行没有目标值，到下一行
            }
        }
        return false;//找不到答案
    }
};

2.二分法(每行左右指针)

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        int col=array[0].size();//矩阵列数
        int row=array.size();//矩阵行数
        if(!col||!row){return false;}
        else
        {
            for(int i=0;i<row;i++)
            {
                if(array[i][0]> target)return false;
                if(array[i][0]== target)return true;
                if(array[i][col-1]== target)return true;
                int low=0,high=col-1;
                int mid=(high+low)/2;
                while(low<mid)
                {
                    if(array[i][mid]==target) return true;
                    if(array[i][mid]<target)//小于目标，右移指针
                    {
                        low=mid;
                        mid=(low+high)/2;
                    }
                    else//大于目标，左移
                    {
                        high=mid;
                        mid=(low+high)/2;
                    }
                }
            }
        }
        return false;//找不到答案
    }
};