10-搜索

题目

01-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

python

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-搜索二维矩阵

leetcode-74

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

逐行二分查找法

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

python

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

python

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-在排序数组中查找元素的第一个和最后一个位置

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]

不纯二分查找左右边界

二分查找左右边界

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

python

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边界值，继续二分向左或右查找边界。

python

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-搜索旋转排序数组

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

python

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-寻找旋转排序数组中的最小值

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

二分查找旋转数组最小值

核心思想

旋转数组，从mid切分，必有一半严格递增。
mid值需和右端点比
若nums[mid] < nums[right]，右边严格递增
- 则最小值在mid或左边，向左收缩，r = mid
若nums[mid] > nums[right]，m-r 发生了旋转断层、下坠点
- 则最小值在mid右边，向右收缩，l=mid+1，mid不可能是最小值。

mid值不能和左端点比

未旋转[1,2,3,4,5]、已旋转[4,5,3,2,1]。
若mid和左侧比较：都是 nums[mid] > nums[left]。无法有效缩减区间。
若mid和右侧比较：
- 前者 nums[mid] < nums[right]：最小值在mid及左侧，向左收缩
- 后者 nums[mid] > nums[right]：最小值在mid右侧，向右收缩

python

def findMin(self, nums: List[int]) -> int:
    """寻找旋转数组最小值"""
    if not nums:
        return 0

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

    # 这块不能<=，只能<，避免死循环，因为r=mid
    while l < r:
        mid = l + (r-l) // 2
        if nums[mid] < nums[r]:
            # 右边递增，最小值在mid或左边，向左收缩
            r = mid
        elif nums[mid] > nums[r]:
            # m-r发生旋转下坠点，最小值在右边，向右收缩，已排除mid是最小值
            l = mid + 1
    # 最终l处，指向最小值
    return nums[l]

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 两个数，算平均值。

二分淘汰

淘汰一半：每次看2个数组的第k/2 数，记为nums1[p1], nums2[p2]，比较谁更小，
- 若nums1[p1] < nums2[p2]：nums1[p1] 最多在合并k-1位，在第k位之前，淘汰 nums1 0-p1 。
- 若 nums1[p1] > nums2[p2]：nums2[p2]最多在k-1位，淘汰 nums2 0-p2 。
更新k继续查找：k = k - 淘汰数量

边界情况

如果1个数组 被淘汰空了：直接返回另一个数组的第k个元素
如果k == 1，比较两个数组的首元素即可。
如果 k/2 越界 大于剩余数组长度，直接取末尾元素进行比较即可。

python

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

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

    def find_kth_element(k: int) -> int:
        """从2个有序数组中，寻找第k小的元素, k>=1"""

        # 遍历起始位置
        idx1, idx2 = 0, 0

        # 循环，进行二分淘汰
        while True:
            # 边界值处理
            # 某个数组已为空，淘汰空了，直接返回另一个数组的第k个元素
            if idx1 == m:
                # nums1 为空
                return nums2[idx2+k-1]
            if idx2 == n:
                # nums2 为空
                return nums1[idx1+k-1]

            # 如果k==1，则比较两个数组的头位置即可
            if k == 1:
                return min(nums1[idx1+k-1], nums2[idx2+k-1])

            # 二分淘汰
            half = k // 2
            p1 = min(idx1 + half, m) - 1
            p2 = min(idx2 + half, n) - 1

            # 注意小于等于，解决相同的情况
            if nums1[p1] <= nums2[p2]:
                # 淘汰nums1[idx1] 及左边
                k = k - (p1 - idx1 + 1)
                idx1 = p1 + 1
            elif nums2[p2] < nums1[p1]:
                # 淘汰nums2[idx2] 左边
                k = k - (p2 - idx2 + 1)
                idx2 = p2 + 1

    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)

题目 ​

01-35-搜索插入位置 ​

二分查找 ​

02-74-搜索二维矩阵 ​

逐行二分查找法 ​

右上角查找法 ​

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

不纯二分查找左右边界 ​

纯二分查找左右边界写法 ​

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

二分查找旋转数组 ​

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

二分查找旋转数组最小值 ​

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

双指针合并数组找中位数 ​

二分淘汰寻找第k小的数 ​

题目

01-35-搜索插入位置

二分查找

02-74-搜索二维矩阵

逐行二分查找法

右上角查找法

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

不纯二分查找左右边界

纯二分查找左右边界写法

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

二分查找旋转数组

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

二分查找旋转数组最小值

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

双指针合并数组找中位数

二分淘汰寻找第k小的数