引言

  二分查找的问题定义为：

给定一个由数字组成的有序数组nums，并给你一个数字target。问nums 中是否存在target。如果存在，则返回其在nums 中的索引。如果不存在，则返回-1。

常见的变体有：

1. 如果存在多个满足条件的元素，返回最左边满足条件的索引。
2. 如果存在多个满足条件的元素,返回最右边满足条件的索引。
3. 数组不是整体有序的。比如先升序再降序，或者先降序再升序。
4. 将一维数组变成二维数组。

我们要注意：二分查找的前提是数组必须是有序的。如果给定数组是无序的，在运用二分查找前需要先排序。

查找一个数

算法描述：

先从数组的中间元素开始，
如果中间元素正好是要查找的元素，则搜索过程结束;
如果目标元素大于中间元素，则在数组大于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。
如果目标元素小于中间元素，则在数组小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。
如果在某一步骤数组为空，则代表找不到。

思维框架：

首先定义搜索区间为[left, right]，注意是左右都闭合,之后会用到这个点。
由于定义的搜索区间为[left, right]，因此当left <= right 的时候，搜索区间都不为空,此时我们都需要继续搜索。也就是说终止搜索条件应该为left <= right。

1. 循环体内，我们不断计算mid，并将nums[mid]与目标值比对。
2. 如果nums[mid]等于目标值，则提前返回mid(只需要找到一个满足条件的即可)
   如果nums[mid]小于目标值，说明目标值在mid右侧，这个时候搜索区间可缩小为[mid + 1, right]
   如果nums[mid]大于目标值，说明目标值在mid左侧，这个时候搜索区间可缩小为[left,mid - 1]
3. 循环结束都没有找到，则说明找不到，返回-1表示未找到

代码实现：

def binary_serach(lis,key):
    low = 0
    high = len(lis) - 1
    # 终止搜索条件是搜索区间为空，定义的搜索区间为闭合区间[low,high]
    # 如果low < high，则搜索区间我[low,high)，此时不会判断low=high的那个元素
    while low <= high:
        mid = int(low +(high - low) / 2)
        if lis[mid] == key:
            return mid
        elif lis[mid] >= key:
            high = mid - 1
        elif lis[mid] <= key:
            low = mid + 1
    # 循环结束条件是搜索空间为空，即数组中不含有目标值
    return -1

if __name__ == '__main__':
    nums = [1, 3, 4, 5, 6, 8, 12, 14, 16]
    target = 8
    result = binary_serach(nums, target)
    print(result)

寻找最左边的满足条件的值

思维框架：

首先定义搜索区间为[left, right]，注意是左右都闭合,之后会用到这个点。
由于定义的搜索区间为[left, right]，因此当left <= right 的时候，搜索区间都不为空,此时我们都需要继续搜索。也就是说终止搜索条件应该为left <= right。

1. 循环体内，我们不断计算mid，并将nums[mid]与目标值比对。
2. 如果nums[mid]等于目标值，则收缩右边界，我们找到了一个备胎，继续看看左边还有没有了
   如果nums[mid]小于目标值，说明目标值在mid右侧，这个时候搜索区间可缩小为[mid + 1, right]
   如果nums[mid]大于目标值，说明目标值在mid左侧，这个时候搜索区间可缩小为[left,mid - 1]
3. 由于不会提前返回，因此我们需要检查最终的left，看 nums[left]是否等于target。
   如果不等于target，或者left出了右边边界了，说明至死都没有找到一个备胎，则返回-1.否则返回left 即可，备胎转正。

def binary_serach(lis, key):
    low, high = 0, len(lis) - 1
    while low <= high:
        mid = int(low + (high - low) / 2)
        # =与>这里可以合并
        if lis[mid] == key:
            # 收缩右边界
            high = mid - 1
        if lis[mid] > key:
            high = mid - 1
        if lis[mid] < key:
            low = mid + 1
    # 如果不等于key，或者left出了右边边界了
    if low >= len(lis) or lis[low] != key:
        return -1
    return low

if __name__ == '__main__':
    nums = [1, 2, 3, 5, 5, 5, 12, 14, 16]
    target = 5
    result = binary_serach(nums, target)
    print(result)

面试题 08.03. 魔术索引

在数组A[0…n-1]中，有所谓的魔术索引，满足条件A[i] = i。给定一个有序整数数组，编写一种方法找出魔术索引，若有的话，在数组A中找出一个魔术索引，如果没有，则返回-1。若有多个魔术索引，返回索引值最小的一个。

示例：

输入：nums = [0, 2, 3, 4, 5]
输出：0
说明: 0下标的元素为0

class Solution:
    def findMagicIndex(self, nums: List[int]) -> int:
        return self.find_magic_index(nums,0,len(nums)-1)
    def find_magic_index(self,nums,left,right):
        # 未找到符合要求的，返回-1
        if left > right:
            return -1
        # 中间元素
        mid = int(left + (right - left) / 2)
        # 看是否能够找到第一个魔术索引，先往左侧找
        left_ans = self.find_magic_index(nums,left,mid-1)
        # 如果左侧存在，那么返回left_ans
        if left_ans != -1:
            return left_ans
        # 如果左侧不存在，先比较nums[mid] == mid
        elif nums[mid] == mid:
            return mid
        # 如果左侧不存在，且nums[mid] ！= mid，往右侧找
        return self.find_magic_index(nums,mid+1,right)

• 时间复杂度：最坏情况下会达到 O(n) 的时间复杂度，其中 n 为数组的长度。
• 空间复杂度：递归函数的空间取决于调用的栈深度，而最坏情况下我们会递归 nn、 层，即栈深度为 O(n)，因此空间复杂度最坏情况下为O(n)。

寻找最右边的满足条件的值

思维框架：

首先定义搜索区间为[left, right]，注意是左右都闭合,之后会用到这个点。
由于定义的搜索区间为[left, right]，因此当left <= right 的时候，搜索区间都不为空,此时我们都需要继续搜索。也就是说终止搜索条件应该为left <= right。

1. 循环体内，我们不断计算mid，并将nums[mid]与目标值比对。
2. 如果nums[mid]等于目标值，则收缩左边界，我们找到了一个备胎，继续看看右边还有没有了
   如果nums[mid]小于目标值，说明目标值在mid右侧，这个时候搜索区间可缩小为[mid + 1, right]
   如果nums[mid]大于目标值，说明目标值在mid左侧，这个时候搜索区间可缩小为[left,mid - 1]
3. 由于不会提前返回，因此我们需要检查最终的right，看 nums[right]是否等于target。
   如果不等于target，或者right出了左边边界了，说明至死都没有找到一个备胎，则返回-1.否则返回right即可，备胎转正。

def binary_serach(lis, key):
    low, high = 0, len(lis) - 1
    while low <= high:
        mid = int(low + (high - low) / 2)
        # =与<这里可以合并
        if lis[mid] == key:
            # 收缩左边界
            low = mid + 1
        if lis[mid] > key:
            high = mid - 1
        if lis[mid] < key:
            low = mid + 1
    # 如果不等于key，或者right出了左边边界了
    if high < 0 or lis[high] != key:
        return -1
    return high

if __name__ == '__main__':
    nums = [1, 2, 3, 5, 5, 5, 12, 14, 16]
    target = 5
    result = binary_serach(nums, target)
    print(result)

寻找最左插入位置

比如一个数组nums: [1,3,4]，target是2。我们应该将其插入（注意不是真的插入）的位置是索引1的位置，即[1,2,3,4]。因此寻找最左插入位置应该返回1，而寻找最左满足条件应该返回-1。

思维框架：

如果你将寻找最左插入位置看成是寻找最左满足大于等于x的值，那就可以和前面的知识产生联系，使得代码更加统一。唯一的区别点在于前面是最左满足等于x，这里是最左满足大于等于x。
具体算法:

1. 首先定义搜索区间为[lIeft, right]，注意是左右都闭合，之后会用到这个点。
   由于我们定义的搜索区间为[left, right]，因此当 left <= right 的时候，搜索区间都不为空。也就是说我们的终止搜索条件为left <= right。
2. 当nums [mid] >= x，说明找到一个备胎，我们令left = mid - 1将 mid 从搜索区间排除，继续看看有没有更好的备胎。
   当nums [mid]<x，说明mid根本就不是答案，直接更新right= mid + 1，从而将mid 从搜索区间排除。
   最后搜索区间left的就是最好的备胎，备胎转正。

def binary_serach(lis, key):
    low, high = 0, len(lis) - 1
    while low <= high:
        mid = int(low + (high - low) / 2)
        if lis[mid] >= key:
            high = mid - 1
        else:
            low = mid + 1
    return low

if __name__ == '__main__':
    nums = [1, 2, 3, 5, 5, 5, 12, 14, 16]
    target = 5
    result = binary_serach(nums, target)
    print(result)

35. 搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。
如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。

示例：

输入: [1,3,5,6], 5
输出: 2

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        begin,end = 0,len(nums) - 1
        while begin <= end:
            mid = int(begin + (end - begin) / 2)
            if nums[mid] > target:
                end = mid - 1
            elif nums[mid] < target:
                begin = mid + 1
            # 在数组中找到目标值，并返回索引
            elif nums[mid] == target:
                return mid
        # 循环结束时，begin > end,此时begin是按顺序插入的位置
        return begin

34. 在排序数组中查找元素的第一个和最后一个位置

给定一个按照升序排列的整数数组 nums，和一个目标值 target。
找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
时间复杂度为 O(log n)

示例：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        # 如果数组为空，返回[-1,-1]
        if not nums:
            return [-1,-1]
        def find(is_find_first):
            left,right = 0,len(nums) - 1
            while left <= right:
                mid = int(left + (right - left) / 2)
                if nums[mid] > target:
                    right = mid - 1
                elif nums[mid] < target:
                    left = mid + 1
                # 说明已经找到了一个nums[mid] == target
                else:
                    # 往左边寻找第一个位置
                    if is_find_first:
                        # 如果nums[mid] == nums[mid -1]，则缩小右边界
                        if mid > 0 and nums[mid] == nums[mid -1]:
                            right = mid - 1
                        else:
                            return mid
                    # 往右边寻找最后一个位置
                    else:
                        # # 如果nums[mid] == nums[mid +1]，则缩小左边界
                        if mid < len(nums) - 1 and nums[mid] == nums[mid +1]:
                            left = mid + 1
                        else:
                            return mid

            return -1
        return [find(True),find(False)]

寻找最右插入位置的情况

如果你将寻找最右插入位置看成是寻找最右满足大于×的值，那就可以和前面的知识产生联系，使得代码更加统一。唯一的区别点在于前面是最右满足等于x，这里是最右满足大于x。

def binary_serach(lis, key):
    low, high = 0, len(lis) - 1
    while low <= high:
        mid = int(low + (high - low) / 2)
        if lis[mid] <= key:
            low = mid + 1
        else:
            high = mid - 1
    return high

if __name__ == '__main__':
    nums = [1, 2, 3, 5, 5, 5, 12, 14, 16]
    target = 5
    result = binary_serach(nums, target)
    print(result)

局部有序(先降后升或先升后降)

33. 搜索旋转排序数组

整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1

思路1：

首先找到旋转点，找到旋转点可以转化成找到最小值，下面是找到最小值的过程：

1. nums[0]<=nums[max]说明整个数组是有序的，下标0就是最小值
2. 如果num[i]>nums[i+1]，不满足升序，说明i+1就是最小值，退出查找
3. 如果中间值nums[mid]>=nums[0]说明数组左边是有序的，最小值应该在右边
4. 如果中间值nums[mid]<nums[0]说明数组左边是无序的，最小值应该在数组左边

找到旋转点后，旋转点两边都是升序数组

如果蓝色部分最小值<=target<=蓝色部分最大值，那么结果肯定是在蓝色部分，又因为这部分是升序的，所以用正常的二分查找就可以找target了。
同理，如果绿色部分最小值<=target<=绿色部分最大值，那就用二分查找在绿色部分进行查找。

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if not nums:
            return -1
        n = len(nums) 
        # 查找最小值的坐标
        def find_min_index():
            begin = 0
            end = len(nums) - 1
            # 如果第一个值比最后一个值小，说明数组是有序的,最小值坐标为begin
            if nums[begin] < nums[end]:
                return begin
            
            while begin <= end:
                mid = int(begin + (end - begin) / 2)
                # 如果num[i]>nums[i+1]，不满足升序，说明i+1就是最小值，退出查找
                if mid < n-1 and nums[mid] > nums[mid +1]:
                    return mid + 1
                # 如果中间点大于第一个点，说明左半边是有序的，旋转点在右边
                if nums[mid] >= nums[0]:
                    begin = mid + 1
                else:
                    end = mid - 1
            return 0
        # 二分查找
        def binary_serach(begin,end):
            while begin <= end:
                mid = int(begin + (end - begin) / 2)
                if nums[mid] == target:
                    return mid
                if nums[mid] > target:
                    end = mid - 1
                else:
                    begin = mid + 1
            return -1
        
        # 首先找到旋转点坐标
        minIndex = find_min_index()
        # 如果最小值坐标为0，则数组是有序的
        if minIndex == 0:
            return binary_serach(0,n-1)
        if target >= nums[0]:
            return binary_serach(0,minIndex-1)
        
        return binary_serach(minIndex,n-1)

思路2:

1. 如果nums[mid]==target，找到目标值直接返回
2. 如果mid左侧是有序的且nums[begin]<=target<=nums[mid]，那么目标值在mid左侧
   如果mid左侧是有序的且taget不在[nums[begin],nums[mid]]范围内，那么目标值在mid右侧
3. 如果mid右侧是有序的且nums[mid]<target<=nums[end]，那么目标值在mid右侧
   如果mid右侧是有序的且target不在[nums[mid],nums[end]]，那么目标值在mid左侧。

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if not nums:
            return -1
        begin = 0
        end = len(nums) - 1
        while begin <= end:
            mid = int(begin + (end - begin) / 2)
            # 找到目标值直接返回
            if nums[mid] == target:
                return mid
            # 如果左侧是有序的
            if nums[begin] <= nums[mid]:
                # 要在左侧有序区间内寻找
                if nums[begin] <= target <= nums[mid]:
                    end = mid - 1
                # 否则，反方向寻找
                else:
                    begin = mid + 1
            # 如果右侧是有序的
            else:
                if nums[mid] < target <= nums[end]:
                    begin = mid + 1
                else:
                    end = mid - 1
        # 循环结束条件是begin > end
        return -1

• 时间复杂度： O(logn)，其中 n 为 nums数组的大小。整个算法时间复杂度即为二分查找的时间复杂度 O(logn)。
• 空间复杂度： O(1) 。我们只需要常数级别的空间存放变量。

81. 搜索旋转排序数组 II

  这个题目与上面那个题目的区别是nums数组中含有重复元素。

已知存在一个按非降序排列的整数数组 nums ，数组中的值不必互不相同。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转 ，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。
给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。

思路：

我们可以先找出mid，然后根据mid来判断,mid是在有序的部分还是无序的部分
假如mid 小于 start，则mid 一定在右边有序部分，即[mid,end]部分有序。
假如mid 大于start，则 mid 一定在左边有序部分，即[start,mid]部分有序。这是这类题目的突破口。
如果mid = start，则往右移动start

class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        left,right = 0,len(nums) - 1
        while left <= right:
            mid = int(left + (right - left) / 2)
            if nums[mid] == target:
                return True
            # 如果左侧与mid相等
            while left < mid and nums[left] == nums[mid]:
                left = left + 1
            # 如果左侧有序
            if nums[left] <= nums[mid]:
                # 如果target在有序部分,则舍弃无序部分
                if nums[left] <= target <= nums[mid]:
                    right = mid - 1
                # 如果在无序部分
                else:
                    left = mid + 1
            # 如果右侧有序
            else:
                if nums[mid] <= target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1
        return False

• 时间复杂度： O(logn)，其中 n 为 nums数组的大小。整个算法时间复杂度即为二分查找的时间复杂度 O(logn)。
• 空间复杂度： O(1) 。我们只需要常数级别的空间存放变量。

面试题 10.03. 搜索旋转数组

  这个题目在上面题目的基础上，要求返回索引值最小的那个，即最左边满足条件的值

搜索旋转数组。给定一个排序后的数组，包含n个整数，但这个数组已被旋转过很多次了，次数不详。请编写代码找出数组中的某个元素，假设数组元素原先是按升序排列的。若有多个相同元素，返回索引值最小的一个。

示例：

输入: arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 5
输出: 8（元素5在该数组中的索引）

class Solution:
    def search(self, arr: List[int], target: int) -> int:
        nums =arr
        left,right = 0,len(nums) - 1
        while left <= right:
            mid = int(left + (right - left) / 2)
            # 如果左边有序
            if nums[left] < nums[mid]:
                # 如果target在有序部分，则去除无序部分
                if nums[left] <= target <= nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            # 如果右边有序
            elif nums[left] > nums[mid]:
                if nums[left] <= target or target <= nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            # 如果left== mid
            elif nums[left] == nums[mid]:
                if nums[left] != target:
                    left = left + 1
                # 如果left == target,此时left是一个备胎，查看其左边是否还有left == target的情况
                else:
                    right = left - 1
        # 最后判断left是否超过右边界并且nums[left] == target
        if left < len(nums) and nums[left] == target:
            return left
        else:
            return -1

153. 寻找旋转排序数组中的最小值

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。
例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

示例：

输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。

思路1：

初始化首尾指针l和r
如果nums[mid]> nums[r]，说明mid在左侧有序部分，由于最小的一定在右侧，因此可以收缩左区间，即l = mid + 1
否则收缩右侧，即r = mid(不可以r = mid - 1)
当l>=r或者nums[l] <nums[r]的时候退出循环
nums[l]< nums[r]，说明区间[l,r]已经是整体有序了，因此nums[l]就是我们想要找的

class Solution:
    def findMin(self, nums: List[int]) -> int:
        left,right = 0,len(nums) - 1
        while left < right:
            # [l,r]有序
            if nums[left] < nums[right]:
                return nums[left]
            mid = int(left + (right - left) / 2)
            # [l,mid]有序，最小值在右侧，收缩左区间
            if nums[mid] > nums[right]:
                left = mid + 1
            # 反之，收缩右区间
            else:
                right = mid 
        return nums[left]

思路2：

我们当然也可以和nums[l]比较，而不是上面的nums[r]，我们发现:

• 旋转点左侧元素都大于数组第一个元素
• 旋转点右侧元素都小于数组第一个元素

因此，我们可以找到数组的中间元素mid。
如果中间元素>数组第一个元素，我们需要在mid右边搜索。
如果中间元素<=数组第一个元素，我们需要在mid左边搜索。

class Solution:
    def findMin(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]
        left,right = 0,len(nums) - 1
        # nums[right] > nums[0]说明数组没有做任何旋转
        if nums[right] > nums[0]:
            return nums[0]
        while left <= right:
            mid = int(left + (right - left) / 2)
            # 找到旋转点
            if nums[mid] > nums[mid+1]:
                return nums[mid + 1]
            if nums[mid -1] > nums[mid]:
                return nums[mid]
            # 说明左侧有序，旋转点在右侧
            if nums[mid] > nums[0]:
                left = mid + 1
            else:
                right = mid - 1

二维数组的二分查找

74. 搜索二维矩阵

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

• 每行中的整数从左到右按升序排列。
• 每行的第一个整数大于前一行的最后一个整数。

示例：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true

思路：

选择矩阵左下角作为起始元素Q
如果Q > target，右方和下方的元素没有必要看了(相对于一维数组的右边元素)
如果Q < target，左方和上方的元素没有必要看了(相对于—维数组的左边元素)
如果Q == target，直接返回True交回了都找不到，返回False

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m,n = len(matrix),len(matrix[0])
        if m == 0:
            return False

        x = m - 1
        y = 0
        while x >= 0 and y < n:
        	# 如果`Q > target`，右方和下方的元素没有必要看了
            if matrix[x][y] > target:
                x -= 1
            # 如果`Q < target`，左方和上方的元素没有必要看了
            elif matrix[x][y] < target:
                y += 1
            else:
                return True
        return False

240. 搜索二维矩阵 II

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

• 每行的元素从左到右升序排列。
• 每列的元素从上到下升序排列。

示例：

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出：true

思路1：起点在左下角

总结出“搜索”的规律是:
如果当前数比目标元素小，当前列就不可能存在目标值，“指针”就向右移一格（纵坐标加1) ;
如果当前数比目标元素大，当前行就不可能存在目标值，“指针”就向上移一格（横坐标减1）。
在编码的过程中要注意数组下标越界的问题

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        rows,cols = len(matrix),len(matrix[0])
        if rows == 0:
            return False
        if cols == 0:
            return False
        
        # 初始坐标为左下角的值
        x = rows - 1
        y = 0
        # 不越界的条件是行大于等于0，列小于等于cols-1
        while x >= 0 and y < cols:
            # 如果当前元素大于target，则不可能在这一行
            if matrix[x][y] > target:
                x -= 1
            # 如果当前元素小于target，则不可能在这一列
            elif matrix[x][y] < target:
                y += 1
            else:
                return True
        return False

思路2：起点在右上角

总结出“搜索”的规律是:
如果当前数比目标元素大，当前列就不可能存在目标值，“指针”就向左移一格(纵坐标减1) ;
如果当前数比目标元素小，当前行就不可能存在目标值，“指针”就向下移一格(横坐标加1)。
在编码的过程中同样要注意数组下标越界的问题。

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        rows,cols = len(matrix),len(matrix[0])
        if rows == 0:
            return False
        if cols == 0:
            return False
        
        # 初始坐标为右上角的值
        x = 0
        y = cols - 1
        # 不越界的条件是列大于等于0，行小于等于rows-1
        while y >= 0 and x < rows:
            # 如果当前元素大于target，则不可能在这一列
            if matrix[x][y] > target:
                y -= 1
            # 如果当前元素小于target，则不可能在这一行
            elif matrix[x][y] < target:
                x += 1
            else:
                return True
        return False

---

如果对您有帮助，麻烦点赞关注，这真的对我很重要！！！如果需要互关，请评论或者私信！

---