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

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数组中s 的计数为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