二分搜索模板

给一个有序数组和目标值，找到第一次/最后一次/任何一次出现的索引，如果没有出现返回-1

模板四点要素：

• 初始化：start = 0，end = len - 1
• 循环退出条件：start + 1 < end
• 比较中点和目标值：A[mid] ==，<，> target
• 判断最后两个元素是否符合：A[start]，A[end]？target

时间复杂度是，使用场景一般是有序数组的查找

二分搜索模板

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        start = 0
        end = len(nums) - 1
        while end - start > 1:
            mid = start + int((end - start)/2)  ###(start + end) // 2
            if nums[mid] > target:
                end = mid
            elif nums[mid] < target:
                start = mid
            else:
                end = mid # 之前一直写的return mid
        if nums[start] == target:
            return start
        elif nums[end] == target:
            return end
        else:
            return -1

搜索二维矩阵

image.png

通过这样，变成一个传统的一维数组的二分查找
重点在于：

row = idx // n
col = idx % n

参考资料：
https://leetcode-cn.com/problems/search-a-2d-matrix/solution/sou-suo-er-wei-ju-zhen-by-leetcode/
https://greyireland.gitbook.io/algorithm-pattern/ji-chu-suan-fa-pian/binary_search