python - 在预排序数组中找到给定值的最低索引

Question

嘿，我在面试中遇到了这个问题，想知道解决它的最佳方法是什么。假设你有一个已经排序的数组，你想找到某个值 x 的最低索引。

这是我想出的 python/伪代码，我只是想知道是否有更好的方法来实现它？

def findLowestIndex(arr, x):
     index = binarySearch(0, len(arr), x)
     if index != -1:
         while index > 0:
           if arr[index] == arr[index-1]:
              index -= 1
           else:
              break
     return index

谢谢!

Answer 1

在最坏的情况下，您的方法需要线性时间，即数组中 x 的计数为 O(n)。

O(lg n) 的解决方案可以通过改变二进制搜索本身来找到数组中的第一个 x 而不是其中的任何一个来获得:

def binary_search(x, a):
    lo = 0
    hi = len(a)

    while lo < hi:
        mid = (lo + hi) // 2

        if a[mid] < x:
            lo = mid + 1
        elif a[mid] > x:
            hi = mid
        elif mid > 0 and a[mid-1] == x:
            hi = mid
        else:
            return mid

    return -1