我试图用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
的数字。
有人能推荐一个更干净的实现吗?我不认为这会是一个如此深奥的问题,尽管我还没有找到任何解决办法。
你试过^{} module 吗?
您的代码错误地认为(1)
low > high
是有效的终止情况。(2) 您不应该停在low == high
处,例如,当num == 3
为您的somenumbers
返回不正确的索引时。如果需要不带对分函数的实现,可以尝试以下代码:
相关问题 更多 >
编程相关推荐