嘿，我在接受采访时有这个问题，并想知道解决问题的最佳方法是什么。所以说你得到一个已经排序的数组，你想要找到某个值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
谢谢！
在最坏的情况下，您的方法需要线性时间，即当数组中的xs计数为O（n）时。
可以通过更改二进制搜索本身来找到数组中的第一个x而不是其中任何一个来获得O（lg n）解决方案：
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
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:
....
但对于面试问题，他们可能想看看你如何提出算法而不是使用图书馆......
如果元素是整数 - 或枚举，你可以更快地做到：
请注意，在二进制搜索[算法，而不是python函数]中，如果元素不存在 - 您可以找到比索引大的最小元素。
x - 并获得索引，让它成为i。x-1。如果它不在列表中，二进制搜索可以找到第一个索引，如果x。j：
在j到i的子列表上进行二分查找，并搜索list[k] < list[k+1]这样的元素对于没有枚举的值，它也可以通过减少范围而list[k] < list[k+1] and list[k+1] == x的相同想法来完成，但我发现首先理解如何对整数进行更简单，然后将其应用于一般解。
请注意，这个解决方案是O(logn)，而你提出的简单解决方案是O(n)，在列表中有很多欺骗，因为二进制搜索后的迭代步骤。
一个递归版本，如果有人感兴趣的话......
来自Algorithms 4th练习的https://github.com/reneargento/algorithms-sedgewick-wayne/blob/master/src/chapter1/section4/Exercise10.java重写。
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？
如果x不在X这样f(x) = v然后答案是微不足道的：二进制搜索找出来。
如果有一个x这样f(x) = v然后答案也是微不足道的：二进制搜索找出来。
如果x有多个f(x) = v，问题就很有趣了。如果存在恒定数量的x，则在算法上二分搜索是最佳的。只需二元搜索并按顺序检查较低的索引。
但是，如果这些x有很多呢？像这样的顺序搜索显然不是最佳的。事实上，如果有c * |X| x，那么这就是在O(|X|)。
相反，可以做的是将lbound初始化为0和二分搜索，直到找到元素，在i，每当你向右走的时候，将lbound更新到刚用过的中间。然后从[lbound, i - 1]二进制搜索。这样做直到i == lbound或你没有找到元素。如果前者发生，所需的指数是0。如果发生后者，则所需的指数是先前使用的i。最糟糕的情况是所需的指数是0。
有趣的是，我认为这仍然在log(|X|)时间运行。
deferred detection of equality approach in binary search给出了最小的索引，减少了平等分支。
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
我敢打赌，g.d.d.c的评论是python的最快答案。否则，您的通用算法是正确的，除了在某些情况下您可以击败二进制搜索的O（log n）行为的事实。具体来说，在整数的情况下，您可以获得的最佳最坏情况行为是O（sqrt（log n））：https://stackoverflow.com/questions/4057258/faster-than-binary-search-for-ordered-list
修改二进制搜索以首次查找x的任何出现。