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

#include <iostream>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param target int整型 
     * @param array int整型vector<vector<>> 
     * @return bool布尔型
     */
    int findTargetArr(int target, vector<int> nums){
	  //二分法
        int l = 0;
        int r = nums.size()-1;
        while (l<=r) {
            int mid = l + (r-l)/2;
            if(nums[mid] < target){
                l = mid + 1; 
            }
            else if(nums[mid] > target){
                r = mid - 1; 
            }
            else{
                return mid;
            }
        }
        return -1;
    }
    bool Find(int target, vector<vector<int>>& array) {
        // write code here
  
        if(array[0].size() == 0 || array.size() == 0){
            return false;
        }
        for(auto & i : array){
            if(findTargetArr(target, i)!=-1)
            {
                return true;
            }
        }
        return false;
    }
};

分别在每一行中采用二分法查找target, 如果在某一行中找到target, 则返回true. 如果在每一行中都没有找到target, 则返回false.

时间复杂度： O(n * logm).