我会使用二进制搜索。您需要查找大于b
的第一个元素或小于b
的最后一个元素。说,我们在一些索引j
找到了更大的第一个元素的索引。那么对于其他情况我们的答案是b [j-1],b [j]等等。这工作在O(logN)时间。
import bisect
def find(a, b):
n, j = len(a), bisect.bisect_left(a, b)
if a[j] > b:
return (None if j == 0 else a[j-1]), a[j]
else:
return a[j], (None if j >= n - 1 else a[j + 1])
if __name__ == '__main__':
a = [4,5,6,8,9,15,16,18,54,60]
b = 24
print find(a, 24)
print find(a, 3)
print find(a, 4)
print find(a, 7)
print find(a, 60)
较短的做法:
import bisect
def find(a, b):
n, j = len(a), bisect.bisect_left(a, b)
return ((None if j == 0 else a[j-1]), a[j]) if a[j] > b else (a[j], (None if j >= n - 1 else a[j + 1]))
重要:数组应该是有序
对不起,我不明白你的问题。如果你看一个数组,你会发现它是排序的,而18是第一个最小的,54是第一个最高的。 –
嗯,我不认为这就是我想要的... –
曾经尝试过我的回复? –