有序含重复元素数组中Floor值查找的O(log₂n)复杂度优化咨询

定义与示例 #

数组中某数值的floor值定义为：数组中小于该数值的最大元素，找到则返回其索引，否则返回-1。

示例数组：arr = [1, 2, 4, 4, 4, 6, 8, 10, 12]

• 案例1：target=4，输出1（arr[1]是小于target的最大元素）
• 案例2：target=13，输出8
• 案例3：target=0，输出-1

问题背景 #

无重复元素的数组中，用常规二分查找后返回high-1就能得到结果，但含重复元素的数组里，普通二分可能定位到target的重复位置，之后需要线性回溯才能找到正确的floor元素，时间复杂度会趋近O(n)。比如target=4时，普通二分可能找到索引4，得回溯到索引1，效率低下。

O(log₂n)复杂度的解决方案 #

可以直接修改二分查找的逻辑，在查找过程中精准定位目标，无需后续回溯。核心是调整指针移动规则，在每次二分判断时记录符合条件的候选值：

算法步骤

1. 初始化左指针left=0，右指针right=len(arr)-1，结果变量res=-1；
2. 当left <= right时循环：
   • 计算中间索引mid = (left + right) // 2；
   • 若arr[mid] < target：当前元素是候选的floor值，记录其索引res=mid，然后尝试寻找更大的候选值，将left=mid+1；
   • 若arr[mid] >= target：当前元素过大，向左缩小查找范围，将right=mid-1；
3. 循环结束后，res即为所求结果。

代码实现（Python）

def find_floor_index(arr, target):
    left = 0
    right = len(arr) - 1
    res = -1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] < target:
            res = mid
            left = mid + 1
        else:
            right = mid - 1
    return res

案例验证

• 针对target=4：循环中会依次记录res=0、res=1，最终返回1，符合预期；
• 针对target=13：最终mid指向8（arr[8]=12<13），res=8，返回正确；
• 针对target=0：所有元素都不小于0，res保持-1，返回正确。

这个算法全程基于二分查找，时间复杂度稳定为O(log₂n)，完全避免了线性回溯的开销。

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