题目

01-35-搜索插入位置

01-35-搜索插入位置

leetcode-35

• 输入：排序不重复数组 nums、目标值target
• 输出：target如果在nums数组中，返回索引，否则返回按顺序插入的位置。
• 要求：$O(\log n)$

二分查找

二分查找

• l=0, r=n-1
• while l <= r 执行循环
  • t == nums[mid]：已找到
  • t > nums[mid]：在右侧，l=mid+1
  • t < nums[mid]：在左侧，r=mid+1

def searchInsert(self, nums: List[int], target: int) -> int:
    """二分查找"""
    n = len(nums)
    # 左右边界
    l, r = 0, n-1
    while l <= r:
        # 中间值
        mid = l + (r-l) // 2
        if target == nums[mid]:
            return mid
        elif target > nums[mid]:
            l = mid + 1
        elif target < nums[mid]:
            r = mid - 1
    # 此时l>r，找不到目标值，left就是需要插入的位置
    return l

02-74-搜索二维矩阵

02-74-搜索二维矩阵

leetcode-74

• 输入：m*n 矩阵，target 整数。矩阵：每行从左到右递增；每行首数 > 上行末数
• 目标：判断target是否在矩阵中。
• 输出：True / False

逐行二分查找法

逐行二分查找法

• 遍历每一行
  • 如果 t < 行尾数：则在行内 做二分查找
  • 如果 t > 行尾数：则continue到下一行

def binary_search(self, nums, target) -> bool:
    """二分查找"""
    if not nums:
        return False

    l, r = 0, len(nums) - 1
    while l <= r:
        mid = l + (r-l)//2
        if target == nums[mid]:
            return True
        elif target > nums[mid]:
            l = mid + 1
        else:
            r = mid - 1
    return False


def searchMatrix_row_binary_search(self, matrix: List[List[int]], target: int) -> bool:
    """逐行二分查找法"""

    if not matrix:
        return False

    m, n = len(matrix), len(matrix[0])

    for i in range(m):
        if target == matrix[i][n-1]:
            return True
        elif target < matrix[i][n-1]:
            # 进行二分查找
            return self.binary_search(matrix[i], target)
        elif target > matrix[i][n-1]:
            # 下一行去查找
            continue
    return False

右上角查找法

右上角查找

• 从右上角开始查找，初始nums[0][n-1]
  • t == nums[i][j]：已找到
  • t > nums[i][j]：往下边找, i=i+1
  • t < nums[i][j]：往左边找，j=j-1

def searchMatrix_rightup_corner(self, matrix: List[List[int]], target: int) -> bool:
    """从右上角开始查找"""
    if not matrix:
        return False 

    m, n = len(matrix), len(matrix[0])

    i, j = 0, n-1

    while 0 <= i < m and 0 <= j < n:
        if target == matrix[i][j]:
            # 已找到
            return True
        elif target < matrix[i][j]:
            # 向左边去找
            j = j - 1
        elif target > matrix[i][j]:
            # 向下一行去找
            i = i + 1
    return False

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

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

leetcode-34

• 输入：非递减 数组nums，目标值t。
• 输出：t在数组中的开始位置和结束位置，若不存在，则返回-1。要求$O(\log n)$
• 示例：
  • [5, 7, 7, 8, 8, 10], t=8 --> [3, 4]
  • [5, 7, 7, 8, 8, 10], t=9 --> [-1, -1]

不纯二分查找左右边界

二分查找左右边界

• 使用二分查找 分别查找 左右边界
• 找到元素后：由于有重复，继续向左或向右 探测边界点。

def searchRange(self, nums: List[int], target: int) -> List[int]:
    """二分查找，左右边界"""
    if not nums:
        return [-1, -1]


    def find_left():
        """查找左边界"""
        l, r = 0, len(nums) - 1

        while l <= r:
            mid = l + (r-l)//2
            if target == nums[mid]:
                # 正常来说，找到目标值，继续往左走，找到左边界
                l = mid 
                while l >= 1 and nums[l] == nums[l-1]:  
                    l = l-1
                return l 
            elif target > nums[mid]:
                l = mid + 1
            elif target < nums[mid]:
                r = mid - 1
        return -1


    def find_right():
        """查找右边界"""
        l, r = 0, len(nums) -1 
        while l<= r:
            mid = l + (r-l)//2
            if target == nums[mid]:
                # 找到目标值，继续往右走，找到右边界
                r = mid 
                while r <= len(nums) - 2 and nums[r] == nums[r+1]:  
                    r += 1
                return r  
            elif target > nums[mid]:
                l = mid + 1
            elif target < nums[mid]:
                r = mid - 1
        return -1

    left, right = find_left(), find_right()  

    return [left, right]

纯二分查找左右边界写法

纯二分查找左右边界

• 使用二分查找 分别查找 左右边界
• 找到元素后：由于有重复，存储mid边界值，继续二分向左或右查找边界。

def searchRange(self, nums: List[int], target: int) -> List[int]:
    """二分查找，左右边界"""
    if not nums:
        return [-1, -1]


    def find_left():
        """查找左边界"""
        l, r = 0, len(nums) - 1
        idx = - 1
        while l <= r:
            mid = l + (r-l)//2
            if target == nums[mid]:
                # 找到目标值，左边界在mid或mid左边，继续收缩边界
                idx = mid  
                r = mid - 1
            elif target > nums[mid]:
                l = mid + 1
            elif target < nums[mid]:
                r = mid - 1
        return idx


    def find_right():
        """查找右边界"""
        l, r = 0, len(nums) -1 
        idx = -1
        while l<= r:
            mid = l + (r-l)//2
            if target == nums[mid]:
                # 找到目标值，右边界在mid或mid右边，继续二分收缩边界
                idx = mid  
                l = mid + 1
            elif target > nums[mid]:
                l = mid + 1
            elif target < nums[mid]:
                r = mid - 1
        return idx  

    left, right = find_left(), find_right()  

    return [left, right]

04-33-搜索旋转排序数组

04-33-搜索旋转排序数组

leetcode-33

• 原nums数组： 升序排列+数值唯一

• 输入：向左旋转后的nums数组；目标值t

• 输出：t在nums中的位置，不存在返回-1，要求O(logn)

• 示例：[4,5,6,7, 0,1,2], t=0 --> 4

向左旋转示例

• 下标3 向左旋转
  • [0,1,2, 4,5,6,7] --> [4,5,6,7, 0,1,2]

旋转数组特性

• 从中间mid切开：左右2部分，必有一半 完全升序，一半包含旋转点。
  • [4,5,6,7, 0,1,2]。l=0, r=6, mid=3

二分严格递增查旋转数组找数

二分查找旋转数组

旋转数组特性

• 从中间mid切开：左右2部分，必有一半 严格递增，一半包含旋转点。

二分核心思想

• 根据严格递增的这个性质，做二分，不断缩小范围；中间值找到直接返回。
• 判断左右2部分 谁严格递增：
  • 若 nums[l] <= nums[mid] 则左边严格递增；否则为右边。
• 左边严格递增
  • 若 t在左边 ：nums[l] <= t < nums[mid]，则r=mid-1，注意此处判断是<=
  • 否则，t在右边：l=mid+1
• 右边严格递增
  • 若 t在右边：nums[mid] < t <= nums[r]，则l=mid+1
  • 否则，t在左边：r=mid-1

def search(self, nums: List[int], target: int) -> int:
    """旋转数组，二分查找，利用旋转数组特性：一半严格递增、一半包含旋转点，每次判断严格递增区间"""

    if not nums:
        return -1

    l, r = 0, len(nums) - 1

    while l <= r:
        mid = l + (r-l) // 2

        # 找到直接返回
        if target == nums[mid]:
            return mid 

        # 左边严格递增
        if nums[l] <= nums[mid]:  
            if nums[l] <= target < nums[mid]:  
                # 在左边区域
                r = mid - 1
            else:
                # 在右边区域
                l = mid + 1
        # 右边严格递增
        else:
            if nums[mid] < target <= nums[r]:  
                # 在右边区域
                l = mid + 1
            else:
                # 在左边区域
                r = mid - 1

    return -1

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

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

leetcode-153

• 数组：元素互不相同、升序排序。
• 输入：经过多次旋转后的数组，即向右旋转
• 输出：最小值，要求$o(\log n)$

向右旋转示例

• 1次旋转 向右移动 1个位置
  • a[0], a[1], ..., a[n-2], a[n-1] --> a[n-1], a[0], a[1], ...., a[n-2]
• 数组[1,2, 3,4,5] ，旋转3次：[3,4,5, 1,2]。
• 数组[0,1,2,4,5,6,7] ，旋转4次：[4,5,6,7,0,1,2]。

旋转数组特性

• 从中间mid切开：左右2部分，必有一半 完全升序，一半包含旋转点。
  • [4,5,6,7, 0,1,2]。l=0, r=6, mid=3

二分查找旋转数组最小值

二分查找旋转数组最小值

核心思想

• 二分查找 + 旋转数组单侧严格递增 + 旋转坠落点 判断最小值。
• l <= r 循环
  • 左侧严格递增：nums[l] <= nums[mid]
    • 若 [mid, r] 存在坠落点：nums[mid] > nums[r]
      • 最小值在 [mid, r] 区间，l=mid+1
    • 否则
      • 最小值在 [l, mid-1] 区间，r=mid-1
  • 右侧严格递增
    • 最小值 在 [l, mid] 区间，r=mid
• 最终返回 nums[l] 为最小值

def findMin(self, nums: List[int]) -> int:
    """升序数组，旋转后，寻找最小值，二分查找"""
    if not nums:
        return -1

    l, r = 0, len(nums) - 1

    # 二分查找最小值
    while l <= r:
        mid = l + (r-l) // 2

        if nums[l] <= nums[mid]:
            # 左边严格递增                
            if nums[mid] > nums[r]:
                # 这个区间，发生下坠点，最小值在这个区间
                l = mid + 1
            else:
                # 最小值在左侧
                r = mid - 1
        else:
            # 右边严格递增
            # 最小值在l-mid 之间
            r = mid

    return nums[l]  

06-4-寻找两个正序数组的中位数

06-4-寻找两个正序数组的中位数

leetcode-4

• 输入：nums1、nums2，都是从小到大排序。
• 输出：两个正序数组的中位数。时间复杂度$O(\log (m+n))$
• 示例：
  • [1, 3], [2] --> 合并数组[1, 2, 3]，中位数2
  • [1, 2], [3, 4] --> 合并数组 [1, 2, 3, 4]，中位数 (2+3)/2=2.5

中位数

• 合并后，长度为$T=m+n$。
• T为奇数：中位数 = nums[T//2 + 1]。
• T为偶数：中位数 = 第T//2 + 第T//2+1 两个数的平均值。

双指针合并数组找中位数

双指针合并数组找中位数

• 双指针 合并数组，谁小放谁，合并后再找中位数
• 时间复杂度为$O(m+n)$，不满足要求

二分淘汰寻找第k小的数

二分查找寻找第k小的数

目标

• 在2个有序数组中，找到第k小的数。
• 实现find_kth(k) 方法。
• 中位数
  • 奇数：寻找第 T//2+1 小的数。
  • 偶数：寻找第 T//2 和 T//2+1 小的数，两数算平均值 为中位数。
  • 注意：此处下标从1开始，第k小。

二分淘汰寻找第k小 find_kth方法

• 核心思想：各看前k//2个数，并比较2个数组中 最后一个数，谁更小，则排除该部分。
• 设置起始偏移量，start1 = start2 = 0，k和start 同时变化。
• while True 二分淘汰循环：
  • 边界处理
    • 若某个数组已经全部排除：则从另一个数组 取第k小
    • 若找第1小：比较两个数组的头部元素，返回更小值。
  • 设置count数：各看前 k // 2 个元素；不够就看剩下的全部。min(k // 2, m - start1)
  • 比较这两段的最后一个元素 value1 和 value2
    • 若value1 <= value2：排除nums1当前看的部分，start1 += count1, k -= count1
    • 若value1 > value2：排除nums2当前看的部分，start2 += count2, k -= count2

def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
    """两个有序数组，寻找中位数。二分，实现findKth方法"""

    m = len(nums1)
    n = len(nums2)

    def find_kth(k: int) -> int:
        """在两个数组中找第 k 小的元素，k 从 1 开始。"""
        start1 = 0
        start2 = 0
				
        # 循环，二分淘汰
        while True:
            # 边界处理：一个数组已经全部排除，直接从另一个数组取第k小
            if start1 == m:
                return nums2[start2 + k - 1]  

            if start2 == n:
                return nums1[start1 + k - 1]

            # 找第 1 小：比较剩余数组的头部。
            if k == 1:
                return min(nums1[start1], nums2[start2])  

            # 各看前 k // 2 个元素；不够就看剩下的全部。
            count1 = min(k // 2, m - start1)  
            count2 = min(k // 2, n - start2)

            # 比较这两段的最后一个元素。
            value1 = nums1[start1 + count1 - 1]  
            value2 = nums2[start2 + count2 - 1]

            if value1 <= value2:  
                # nums1 这一段可以排除。
                start1 += count1  
                k -= count1  
            else:
                # nums2 这一段可以排除。
                start2 += count2 
                k -= count2 

    total_len = m + n
    # 偶数，注意k>=1
    if total_len % 2 == 0:
        v1 = find_kth_element(total_len // 2 + 1)  
        v2 = find_kth_element(total_len // 2)  
        return (v1+v2) / 2
    # 奇数，注意k>=1
    else:
        return find_kth_element(total_len // 2 + 1)