暴力搜索

逐行逐列查找

复杂度分析： 时间复杂度：O(MN) 空间复杂度：O(1)

class Solution:
    def Find(self , target: int, array: List[List[int]]) -> bool:
        arr_line=len(array)
        if array[0]:
            arr_row=len(array[0])
            for i in range(arr_line):
                for j in range(arr_row):
                    if target==array[i][j]:
                        return True
            return False
        else:
            return False

          #暴力搜索2
        if array[0]:
            for a in array:
                if target in a:
                    return True
            return False
        else:
            return False

二分搜索（对数搜索）

一种在有序数组中查找某一特定元素的搜索算法

每次比较都使搜索范围缩小一半

复杂度分析：时间复杂度O(Mlog2N)

步骤

已排好序的数组A[n], 其中 A[0] <= A[1] <= ... <= A[n],以及一个待查找的值K。

步骤：

1. 令low = 0， high = n - 1，初始的查找区域为[low， high]

2. 取low和high的中间值mid = (low+high)/2

3. 如果A[mid] = K，则返回mid, 如果不等，则重新确定查找区间

4. 当low > high 时，则表示区间已经失效，如果还未找到，则表示数组中不包含K的值，返回-1。

重新确定查找区间的规则：

1. 如果A[mid] < K, 则由数组的有序性可知T应该存在于[mid+1, high]之间。

2. 同理，如果A[mid] > K, 则T应该存在于[low, mid-1]区间。

arr_line=len(array)
        if array[0]:
            arr_row=len(array[0])
            for i in range(arr_line):
                left=0
                right=arr_row-1
                while(left<=right):
                    mid=int((left+right)/2)
                    if target == array[i][mid]:
                        return True
                    elif target<array[i][mid]:
                        right=mid-1
                    else:
                        left=mid+1
            return False
        
        else:
            return False

杨氏矩阵搜索

杨氏矩阵：有序二维矩阵——每行从左到右递增，每列从上到下递增

查找算法：从矩阵的左下角或右上角开始递归

复杂度分析：时间复杂度可以达到O(m+n)

步骤

已排好序的数组A[m,n],以及一个待查找的值K

1.初始位置(m-1,0)

2.a[i,j]>K，说明要向上移动一行；如果a[i,j]<K，说明要向右移动一列；a[i,j]=K，则发挥当前位置

3.如果超出矩阵范围，则说明不存在这样的元素，返回(-1,-1)

       arr_line=len(array)
        if array[0]:
            arr_row=len(array[0])
            line=arr_line-1
            row=0
            while (row<arr_row and line>=0):
                if target==array[line][row]:
                    return True
                elif target>array[line][row]:
                    row+=1
                elif target<array[line][row]:
                    line-=1

            return False     
            
        else:
            return False