初始状态：[1, 3, 5, 7]     L=0 R=3
              ↑
             mid=1, nums[1]=3 < 6 → L更新为2

状态2：    [1, 3, 5, 7]        L=2 R=3
                 ↑
                mid=2, nums[2]=5 < 6 → L更新为3

状态3：    [1, 3, 5, 7]           L=3 R=3
                 ↑
                mid=3, nums[3]=7 >= 6 → R更新为2

终止：L=3, R=2 → L > R，退出循环
返回 L=3，即第一个 >= 6 的元素是 nums[3]=7

def lower_bound(nums, target):
    """
    查找第一个 >= target 的元素下标
    :param nums: 有序数组（从小到大）
    :param target: 目标值
    :return: 第一个 >= target 的下标，如果不存在返回数组长度
    """
    n = len(nums)
    # 初始化：L=0 指向搜索区间左端，R=n-1 指向右端
    # 此时 L-1（索引-1，不存在）可视为红色边界
    # R+1（索引n，不存在）可视为蓝色边界
    left, right = 0, n - 1

    # 循环条件：left <= right 表示搜索区间不为空
    # 循环不变量始终成立：
    #   - 索引 < left 的元素都 < target（红色）
    #   - 索引 > right 的元素都 >= target（蓝色）
    while left <= right:
        # 防止 (left + right) 溢出的写法
        # mid = (left + right) // 2  # 可能溢出
        mid = left + (right - left) // 2  # 安全写法

        if nums[mid] < target:
            # nums[mid] < target，说明 mid 及左侧都是红色
            # 蓝色区域一定在 [mid+1, right]，更新 left
            left = mid + 1
        else:
            # nums[mid] >= target，说明蓝色区域在 [left, mid]
            # 更新 right 为 mid-1，继续在左半部分找第一个蓝色
            right = mid - 1

    # 循环结束后，left 指向第一个蓝色元素的位置
    # 此时 left == right + 1
    # 如果所有元素都 < target，left 会等于 n
    return left

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)

        # 第一次二分：找第一个 >= target 的位置（start）
        start = 0
        right = n - 1
        while start <= right:
            mid = start + (right - start) // 2
            if nums[mid] < target:
                start = mid + 1
            else:
                right = mid - 1
        # start 就是第一个 >= target 的位置
        # 但需要验证这个位置是否真的等于 target
        if start == n or nums[start] != target:
            return [-1, -1]

        # 第二次二分：找第一个 > target 的位置（end+1）
        end = 0
        right = n - 1
        while end <= right:
            mid = end + (right - end) // 2
            if nums[mid] <= target:
                end = mid + 1
            else:
                right = mid - 1
        # end 是第一个 > target 的位置，所以 end-1 是最后一个 = target 的位置
        return [start, end - 1]

class Solution:
    def maximumCount(self, nums: List[int]) -> int:
        n = len(nums)

        # 第一次二分：找第一个 >= 0 的位置（负数分界点）
        l, r = 0, n - 1
        pos1 = n  # 默认值：如果所有数都 < 0，负数个数为 n
        while l <= r:
            mid = (l + r) // 2
            if nums[mid] >= 0:
                pos1 = mid      # 记录第一个 >= 0 的位置
                r = mid - 1     # 继续在左半部分找
            else:
                l = mid + 1
        neg = pos1  # 索引 [0, pos1) 都是负数

        # 第二次二分：找第一个 > 0 的位置（正数分界点）
        l, r = 0, n - 1
        pos2 = n  # 默认值：如果所有数都 <= 0，正数个数为 0
        while l <= r:
            mid = (l + r) // 2
            if nums[mid] > 0:
                pos2 = mid      # 记录第一个 > 0 的位置
                r = mid - 1     # 继续在左半部分找
            else:
                l = mid + 1
        pos = n - pos2  # 索引 [pos2, n) 都是正数

        return max(neg, pos)

class Solution:
    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
        potions.sort()  # 排序，为二分查找做准备
        n = len(spells)
        m = len(potions)
        pairs = [0] * n

        for x, y in enumerate(spells):
            # 对于当前咒语 y，计算满足条件的最小药水强度
            # spell * potion >= success → potion >= success / spell
            # 找第一个 >= success/y 的位置
            left, right = 0, m - 1
            while left < right:
                mid = (left + right) // 2
                if potions[mid] * y >= success:
                    right = mid  # 满足条件，继续在左半部分找更小的
                else:
                    left = mid + 1  # 不满足，左移右边界

            # 判断找到的位置是否真的满足条件
            if potions[left] * y >= success:
                pairs[x] = m - left  # 从该位置到末尾都满足
            else:
                pairs[x] = 0

        return pairs

class Solution:
    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:
        arr1.sort()  # 排序
        arr2.sort()
        ans = j = 0

        for x in arr1:
            # 在 arr2 中找第一个 >= x-d 的位置
            # 利用 arr2 单调性，指针 j 只增不减
            while j < len(arr2) and arr2[j] < x - d:
                j += 1
            # 判断 arr2[j] 是否超出 x+d 的范围
            # 如果 j 已到末尾，或 arr2[j] > x+d，则 x 符合距离要求
            if j == len(arr2) or arr2[j] > x + d:
                ans += 1

        return ans