数组查找

题目描述

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

解决思路

• 暴力解法，时间复杂度
• 二叉查找法 ，时间复杂度
• 利用二维数组由上到下，由左到右递增的规律，那么选取左下角或者右上角的元素a[i][j]与target进行比较，当target大于元素a[i][j]时，那么target必定在元素a所在行的右边,即j++；当target大于元素a[i][j]时，那么target必定在元素a所在列的上边,即i--；时间复杂度

我的代码

思路二

class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        """二分查找法"""
        m=len(array);
        n=len(array[0])
        for i in range(m):
            left=0;
            right=n-1;
            while (left<=right):
                middle=(left+right)//2;
                if (target>array[i][middle]):
                    left=middle+1;
                elif (target<array[i][middle]):
                    right=middle-1;
                else:
                    return True;
            return False

思路三

class Solution:
    # array 二维列表 target 一个数
    def Find(self, target, array):
        """ 查找二维数组array中是否存在target,存在返回True,不存在返回False"""

        m=len(array);
        n=len(array[0]);
        i,j=0,n-1;

        #取右上角为第一个开始比较
        while (i<=n-1 and j>=0):#表示在这个数的下面
            if (target>array[i][j]):
                i=i+1;
            elif (target<array[i][j]):#表示在这个数的右面
                j=j-1;
            else:
                return True;#相等
        return False;