题解 | #二维数组中的查找#

1.使用二分查找

class Solution {
public:
    bool binarySearch(vector<int> &nums,int target)
    {
        int low = 0;
        int high = nums.size()-1;
        while(low <= high)
        {
            int mid = (low + high)/2;
            if(nums[mid] > target)
                high = mid-1;
            else if(nums[mid] < target)
                low = mid+1;
            else
                return true;
        }
        return false;
    }
    bool Find(int target, vector<vector<int> > array) {
        for(int i = 0;i<array.size();++i)
        {
            if(binarySearch(array[i],target))
                return true;
        }
        return false;
    }
};

2.根据矩阵的规律来解：左下元素大于它上方的元素，小于它右方的元素，右上元素与之相反

具体做法：

• step 1：首先获取矩阵的两个边长，判断特殊情况。
• step 2：首先以左下角为起点，若是它小于目标元素，则往右移动去找大的，若是他大于目标元素，则往上移动去找小的。
• step 3：若是移动到了矩阵边界也没找到，说明矩阵中不存在目标值

class Solution {
public:
    bool binarySearch(vector<int> &nums,int target)
    {        
		int n = array.size()-1;
        int m = array[0].size()-1;
        for(int i = n,j = 0;i >= 0 && j<=m;)
        {
            if(array[i][j] < target)
                j++;
            else if(array[i][j]>target)
                i--;
            else 
                return true;
        }
        return false;
	}
};