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数组中 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

Answer 2

import bisect
l = [1,2,3,4,4,4,4,4,5,5,5,5,5,6,6,7,7,7,8,8]
bisect.bisect_left(l, 4)

编辑：我只是想念一件事。bisect 会给你一个插入点。因此，如果 x 不在列表中，您仍然会有一个结果索引。所以你需要先检查 x 是否在列表中：

if x in l:
    ....

但是对于面试问题，他们可能想看看你是如何提出算法而不是使用库的......

Answer 3

如果元素是整数- 或枚举，你可以做得更快一点：

请注意，在二进制搜索[算法，而不是 python 函数]中，如果一个元素不存在 - 你可以找到比索引大的最小元素。

1. 首先搜索x- 并获取索引，让它成为i.
2. 接下来，搜索x-1. 如果它不在列表中，则二进制搜索可以找到您的第一个索引 if x。
3. 如果它在列表中，则让找到的索引为j：
   • 对子列表 from jto进行二分搜索i，并搜索一个元素，使得list[k] < list[k+1]

对于未枚举的值，也可以通过减小范围的相同想法来完成，list[k] < list[k+1] and list[k+1] == x但我发现首先理解它是如何处理整数的，然后将其应用于一般解决方案更简单。

请注意，此解决方案是O(logn)，而您提出的简单解决方案是O(n)，在有很多欺骗的列表中，因为二分搜索之后的迭代步骤。

Answer 4

递归版本，如果有人感兴趣...

从https://github.com/reneargento/algorithms-sedgewick-wayne/blob/master/src/chapter1/section4/Exercise10.java重写，来自Algorithms 4th的练习。

def binary_search(key, a, low, high):
    if low > high:
        return -1;
    middle = low + (high - low) / 2;
    if a[middle] < key:
        return binary_search(key, a, middle + 1, high)
    elif a[middle] > key:
        return binary_search(key, a, low, middle - 1)
    else:
        if (middle - 1 >= 0) and (a[middle - 1] != key):
            return middle
        else:
            index = binary_search(key, a, 0, middle - 1)
            if(index == -1):
                return middle;
            else:
                return index;

a = [1,2,3,3,3,3,4,5,6,7,7,8,9]

print(binary_search(7, a, 0, len(a)))

递归版本不是总是比非递归版本更简单吗？为什么这看起来更难..？谁能写一个更好的递归版本：D？

Answer 5

如果x不是X这样，f(x) = v那么答案是微不足道的：二进制搜索来找出答案。

如果有x这样一个，f(x) = v那么答案也是微不足道的：二分搜索找出答案。

这个问题只有在有多个x这样的情况下才是有趣的f(x) = v。如果x's 的数量是恒定的，那么从算法上讲，二分搜索是最佳的。只需二进制搜索并按顺序检查较低的索引。

但是，如果有很多这样x的 怎么办？像这样的顺序搜索显然不是最优的。事实上，如果有c * |X| x's 那么这运行在O(|X|).

相反，可以做的是初始化并lbound进行0二分搜索，直到找到元素 at i，每次向右时，更新lbound到刚刚使用的中间值。然后从[lbound, i - 1]. 这样做直到i == lbound找不到元素。如果发生前者，则所需索引为0。如果发生后者，则所需的索引是先前i使用的。最坏的情况是所需的索引是0。

有趣的是log(|X|)，我认为这仍然会及时运行。

Answer 6

二进制搜索中相等方法的延迟检测给出最小索引，减少相等分支。

def binary_search(low, high, target, array):
    while low < high:
        mid = low + (high - low) / 2
        if a[mid] < target:
            low = mid + 1
        else:
            high = mid

    if (array[low] == target) return low
    else return -1

Answer 7

我敢打赌gddc的评论是python最快的答案。否则，您的一般算法是正确的，除了在某些情况下您可以击败二进制搜索的 O(log n) 行为。具体来说，在整数的情况下，您可以获得的最佳最坏情况行为是 O(sqrt(log n))： https ://stackoverflow.com/questions/4057258/faster-than-binary-search-for-ordered-列表

Answer 8

修改二分搜索以首次找到任何出现的 x。