我正在尝试在 Python 中编写一个函数,该函数在排序列表中找到大于我作为参数传入的特定值的第一个数字。我在网上找到了使用简单列表推导来实现此目的的示例,但出于我的目的,我需要经常在大型列表上执行此操作,因此在线性时间内运行的搜索成本太高。
尽管我遇到了一些无法正常工作的边缘情况,但我在编写类似迭代二进制搜索的函数来实现这一点方面已经有了突破。顺便说一句,该函数不需要处理列表中没有更大项目的情况。这是我现有的功能:
def findFirstLarger(num, sortedList):
low = 0;
high = len(sortedList) - 1
mid = -1
while True:
print("low: " + str(low) + "\t high: " + str(high))
if (low > high):
print("Ah geez, low is " + str(low) + " and high is " + str(high))
return # debugging, don't want this to happen
if low == high:
return sortedList[low]
else:
mid = (low + high) / 2;
if num == sortedList[mid]:
return sortedList[mid]
elif num > sortedList[mid]:
low = mid + 1
else:
high = mid - 1
我注意到此功能不起作用的一种情况如下:
>>> somenumbers=[n*2 for n in range(131072)]
>>> somenumbers[-5:]
[262134, 262136, 262138, 262140, 262142]
>>> binsearch.findFirstLarger(262139,somenumbers)
low: 0 high: 131071
low: 65536 high: 131071
low: 98304 high: 131071
low: 114688 high: 131071
low: 122880 high: 131071
low: 126976 high: 131071
low: 129024 high: 131071
low: 130048 high: 131071
low: 130560 high: 131071
low: 130816 high: 131071
low: 130944 high: 131071
low: 131008 high: 131071
low: 131040 high: 131071
low: 131056 high: 131071
low: 131064 high: 131071
low: 131068 high: 131071
low: 131070 high: 131071
low: 131070 high: 131069
Ah geez, low is 131070 and high is 131069
这里正确的结果是262140
,因为这是列表中大于 的第一个数字262139
。
任何人都可以推荐一个更干净的实现吗?我不认为这会是一个如此深奥的问题,尽管到目前为止我还没有在任何地方找到解决方案。