每日一道算法题--二维数组中的查找--python

【题目描述】

思路一：按行执行二分查找，只要该行的第一个元素小于目标，就对该行二分查找。 思路二：从数组的左下角array[j][i]开始查找，如果当前值小于目标，就向右，即i+1;如果当前值大于目标，就向上，即j-1。

【源代码】

思路1:时间复杂度0(nlogn)
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        if(len(array)==0 or len(array[0])==0):return False
        for i in range(0,len(array)):
            if(array[i][0]>target):
                break
            num=array[i]
            left=0
            right=len(num)-1
            while left<=right:
                mid=int((left+right)/2)
                if(num[mid]>target):
                    right=mid-1
                elif(num[mid]<target):
                    left=mid+1
                else:
                    return True
        return False
                
复制代码

思路2:时间复杂度：O(n)

class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        rows = len(array) - 1
        cols= len(array[0]) - 1
        i = rows
        j = 0
        while j<=cols and i>=0:
            if target<array[i][j]:
                i -= 1
            elif target>array[i][j]:
                j += 1
            else:
                return True
        return False
复制代码