含重复元素的有序数组区间查找问题（二分法求解咨询）

问题明确 #

给定非递减有序且包含重复元素的数组arr，以及输入值x_input，需要找到满足arr[i] < x_input <= arr[j]的相邻下标[i, j]，同时需遵循两个规则：

• 若右侧存在与arr[j]重复的元素，j必须是这些重复元素中的最小下标
• 若左侧存在与arr[i]重复的元素，i必须是这些重复元素中的最大下标
• 特殊情况：当x_input大于所有元素时，j为数组长度；当x_input小于所有元素时，i为-1

示例数组：arr = [-2, -1, -1, -1, 2, 2, 5]
测试用例：

• x_input = -1.5 → 返回[0, 1]
• x_input = -1 → 返回[0, 1]
• x_input = 2 → 返回[3, 4]
• x_input = 2.1 → 返回[6, 7]

核心思路 #

利用二分查找的变体，分别定位两个关键边界：

1. 找j的位置：第一个大于等于x_input的元素下标（若所有元素都小于x_input，则j = len(arr)）
2. 找i的位置：最后一个小于x_input的元素下标（若所有元素都大于x_input，则i = -1）

这两个边界的定位都可以通过二分查找高效完成，时间复杂度为O(log n)，远优于线性遍历的O(n)。

具体实现步骤 #

步骤1：定位j（第一个>=x_input的下标） #

• 初始化左右指针left=0，right=len(arr)（右边界设为数组长度，覆盖所有元素都小于x_input的情况）
• 循环条件left < right：
  • 计算中间下标mid = (left + right) // 2
  • 若arr[mid] >= x_input：说明目标j在mid或左侧，更新j=mid，并将右指针移到mid
  • 若arr[mid] < x_input：说明目标j在mid右侧，将左指针移到mid+1

步骤2：定位i（最后一个<x_input的下标） #

• 初始化左右指针left=0，right=len(arr)-1
• 循环条件left <= right：
  • 计算中间下标mid = (left + right) // 2
  • 若arr[mid] < x_input：说明当前mid是候选i，可能还有更大的下标满足条件，更新i=mid，并将左指针移到mid+1
  • 若arr[mid] >= x_input：说明目标i在mid左侧，将右指针移到mid-1

代码示例（Python） #

def find_bound_indices(arr, x_input):
    n = len(arr)
    # 找j：第一个 >= x_input 的下标
    left, right = 0, n
    j = n
    while left < right:
        mid = (left + right) // 2
        if arr[mid] >= x_input:
            j = mid
            right = mid
        else:
            left = mid + 1
    
    # 找i：最后一个 < x_input 的下标
    i = -1
    left, right = 0, n - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] < x_input:
            i = mid
            left = mid + 1
        else:
            right = mid - 1
    
    return [i, j]

# 测试用例验证
arr = [-2, -1, -1, -1, 2, 2, 5]
print(find_bound_indices(arr, -1.5))  # [0, 1]
print(find_bound_indices(arr, -1))     # [0, 1]
print(find_bound_indices(arr, 2))      # [3, 4]
print(find_bound_indices(arr, 2.1))    # [6, 7]

参考LeetCode题目 #

这些题目可以帮助你巩固二分查找处理边界的思路：

• 34. 在排序数组中查找元素的第一个和最后一个位置：练习定位重复元素的左右边界，和本题的核心逻辑高度相似
• 35. 搜索插入位置：练习找第一个大于等于目标值的下标，对应本题中j的定位逻辑
• 704. 二分查找：掌握基础二分查找的框架，理解指针收缩的逻辑

内容的提问来源于stack exchange，提问作者dhs4402