二分查找练习

1、请实现无重复数字的升序数组的二分查找
给定一个 元素升序的、无重复数字的整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标（下标从 0 开始），否则返回 -1
数据范围：0 ≤len(nums)≤2×10^5， 数组中任意值满足:∣val∣≤10^9
进阶：时间复杂度 O(logn) ，空间复杂度 O(1)
示例1
输入：[-1,0,3,4,6,10,13,14],13
返回值：6
说明：13 出现在nums中并且下标为 6
示例2
输入：[],3
返回值：-1
说明：nums为空，返回-1
示例3
输入：[-1,0,3,4,6,10,13,14],2
返回值：-1
说明：2 不存在nums中因此返回 -1

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param nums int整型一维数组 
# @param target int整型 
# @return int整型
#
class Solution:
    def search(self , nums: List[int], target: int) -> int:
        # write code here
        # 方式一
        result = self.func_one(nums, target)
        # 方式二
        result = self.func_two(nums, target)
        # 方式三
        result = self.func_three(nums, target, 0, len(nums)-1)
        return result
        
    def func_one(self , nums: List[int], target: int) -> int:
        """in 的方式"""
        target_index = -1
        if nums !=[] and target in nums:
            target_index = nums.index(target)
            return target_index
        else:
            return target_index

    def func_two(self , nums: List[int], target: int) -> int:
        """迭代的方式"""
        start = 0
        end = len(nums) - 1
        middle = 0
        while start <= end:
            middle = (start + end) // 2
            if target == nums[middle]:
                return middle
            elif target < nums[middle]:
                end = middle - 1
            else:
                start = middle + 1
        return -1
    
    def func_three(self , nums: List[int], target: int, start:int, end:int) -> int:
        """递归方式"""
        if start > end :
            return -1
        
        mid = (start + end) // 2
        if nums[mid] > target:
            return self.func_three(nums, target, start, mid-1)
        elif nums[mid] < target:
            return self.func_three(nums, target, mid+1, end)
        else:
            return mid

描述
在一个二维数组array中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
[
[1,2,8,9],
[2,4,9,12],
[4,7,10,13],
[6,8,11,15]
]
给定 target = 7，返回 true。
给定 target = 3，返回 false。
数据范围：矩阵的长宽满足 5000≤n,m≤500 ， 矩阵中的值满足10^90≤val≤10
9
进阶：空间复杂度 O(1)，时间复杂度 O(n+m)

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param target int整型 
# @param array int整型二维数组 
# @return bool布尔型
#
class Solution:
    def Find(self , target: int, array: List[List[int]]) -> bool:
        # write code here
        # 方式一:直接遍历使用i判断
        result = False
        for a in array:
            if target in a:
                return True
        # 方式二：通过二分法迭代查找
        result = False
        for a in array:
            result = self.func(a, target)
            if result:
                return True
        return result
    
        # 方式三：杨氏矩阵查找法，从左下角开始
        result = self.func_two(target, array)
        return result
    
    def func(self, nums: list, target:int) -> bool:
        """迭代"""
        start = 0
        end = len(nums) -1
        while start <= end:
            mid = (start + end) // 2
            if target == nums[mid]:
                return True
            elif target > nums[mid]:
                start = mid + 1
            else:
                end = mid -1
        return False
    
    def func_two(self, target: int, array: List[List[int]]) -> bool:
        """杨氏矩阵查找"""
        len_m = len(array)
        len_n = len(array[0])
        i = len_m - 1
        j = 0
        while i >= 0 and j <= len_n - 1:
            if target == array[i][j]:
                return True
            elif target > array[i][j]:
                j += 1
            else:
                i -= 1
        return False