35. 搜索插入位置

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

Solution

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        low = 0
        high = len(nums) - 1
        while low <= high:
            i = (low + high) // 2
            if target < nums[i]:
                high = i - 1
            elif target > nums[i]:
                low = i + 1
            else:
                return i
        return low

在target大于nums[i]的情况下，你应该让low变为i+1，因为你已经知道nums[i]不等于target，所以下一次循环应该从i+1开始查找。同理，如果target小于nums[i]，你应该让high变为i-1，因为你已经知道nums[i]不等于target，所以下一次循环应该查找到i-1。

while循环的条件应该为low <= high，因为当low和high指向同一个元素时，我们仍然需要检查这个元素是否等于目标值。如果while循环的条件为low < high，那么当low和high指向同一个元素时，循环就会结束，可能会漏掉这个元素。

当我们在二分查找中没有找到目标值时：

如果目标值比所有数组元素都大，那么搜索将结束在low指针指向数组末尾之后的位置，high指针将在数组的最后一个元素。此时返回low是正确的，因为这是目标值应插入的位置。
如果目标值比所有数组元素都小，那么搜索将结束在low指针指向数组的第一个元素，high指针将在数组的起始位置之前。此时返回low也是正确的，因为这是目标值应插入的位置。
如果目标值在数组的中间位置并且没有找到，那么low指针将指向大于目标值的最小元素，high指针将指向小于目标值的最大元素。此时返回low同样是正确的，因为这是目标值应插入的位置。

74. 搜索二维矩阵

给你一个满足下述两条属性的 m x n 整数矩阵：

每行中的整数从左到右按非递减顺序排列。
每行的第一个整数大于前一行的最后一个整数。

给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

Solution

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m, n = len(matrix), len(matrix[0])
        low_i, high_i, low_j, high_j = 0, m-1, 0, n-1

        while low_i <= high_i:
            i = (low_i + high_i) // 2
            if matrix[i][0] == target:
                return True
            elif matrix[i][0] < target:
                low_i = i + 1
            else:
                high_i = i - 1
        
        while low_j <= high_j:
            j = (low_j + high_j) // 2
            if matrix[high_i][j] == target:
                return True
            elif matrix[high_i][j] < target:
                low_j = j + 1
            else:
                high_j = j - 1

        return False

若将矩阵每一行拼接在上一行的末尾，则会得到一个升序数组，我们可以在该数组上二分找到目标元素。假设有 m 行 n 列的二维数组，那么一维索引 mid 对应的二维索引就是 (mid // n, mid % n)。使用 divmod() 函数可以更加方便地得到这两个值。

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix:
            return False

        m, n = len(matrix), len(matrix[0])
        low, high = 0, m * n - 1

        while low <= high:
            mid = (low + high) // 2
            row, col = divmod(mid, n)
            
            if matrix[row][col] == target:
                return True
            elif matrix[row][col] < target:
                low = mid + 1
            else:
                high = mid - 1
        
        return False