二分

二分查找

35. 搜索插入位置：leetcode.cn/problems/search-insert-position/

给定一个排序数组和一个目标值，找到目标值并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。时间复杂度为 O(log n)。

思路与解答：

本题可通过lower_bound来实现。以下是常见的二分查找变种，适用于整数域中的查找：

1. 第一个 >= x ：lower_bound(x)
2. 第一个 > x ：lower_bound(x + 1)
3. 最后一个 <= x ：lower_bound(x + 1) - 1
4. 最后一个 < x ：lower_bound(x) - 1

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        def lower_bound(nums, target):
            l, r = 0, len(nums) - 1
            while l <= r:
                mid = l + (r - l) // 2
                if nums[mid] < target:
                    l = mid + 1
                else:
                    r = mid - 1
            return l
        return lower_bound(nums, target)

复杂度分析：

• 时间复杂度：O(log n)，每次查找都将搜索范围缩小一半。
• 空间复杂度：O(1)，只使用了常数级的空间。

34. 在排序数组中查找元素的第一个和最后一个位置：leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/

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

思路与解答：

使用 lower_bound 来查找边界。

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def lower_bound(nums, target):
            l, r = 0, len(nums) - 1
            while l <= r:
                mid = l + (r - l) // 2
                if nums[mid] < target:
                    l = mid + 1
                else:
                    r = mid - 1
            return l
        
        l = lower_bound(nums, target)
        if l == len(nums) or nums[l] != target:
            return [-1, -1]
        r = lower_bound(nums, target + 1) - 1
        return [l, r]

复杂度分析：

• 时间复杂度：O(log n)，每次二分查找的时间复杂度为 O(log n)。
• 空间复杂度：O(1)，只使用了常数级的空间。