我有这个功能f(n) = x
使用二分查找来查找可能不存在的 x。问题是,f(n)
区分偶数和奇数,例如 f(x) < f(x+2)
是有保证的,但是f(x) < f(x+1)
不是。
有限列表示例:
x = [0,1,1,2,3,5,4,7,6,8,13]
x[5] < x[7] but f[5] > f[6]
目前我进行了两次单独的二进制搜索,一次用于偶数,一次用于大写:
def binarySearch(n, lower, upper, even):
mid = (upper+lower)//2
if even:
if mid % 2 != 0:
mid += 1
else:
if mid % 2 != 1:
mid += 1
...
但要确保mid
偶数或奇数给我带来了停止的问题,并且我产生了 StackOverflows。我在哪里以及如何确保这种情况不会发生?
奖励:如何在不使用两个单独的二进制搜索的情况下解决这个问题?
最佳答案
如果数组不是那么大,这意味着额外的内存空间是可以接受的。我建议您在二分搜索之前将数组分开,因为这样可以使问题更容易。
odd_list = x[::2]
even_list = x[1::2]
此外,您甚至可以使用bisect直接用于排序数组。
否则,我不知道您的停止问题是什么,因为我没有看到您的退出代码。但是,您可以做的是:
if (lower % 2 == 0) != even:
lower += 1
if (upper % 2 == 0) != even:
upper -= 1
if lower > upper:
return -1
mid = get_mid_wth_lower_and_upper() // your code
if x[mid] == n:
return mid
elif x[mid] < n:
return binarySearch(n, mid + 2, upper, even)
else:
return binarySearch(n, lower, mid - 2, even)
请注意,此处的 upper 表示最后一个元素的 index
,而不是 index+1
。如果这不是您的情况,则需要进行一些小的更改。
其实和普通的二分查找没有太大区别。对于普通数组,边缘情况是具有 0、1 或 2 个元素的数组,而这里则变为 0、1 或 3。
关于python - 二分查找函数,取决于偶数和奇数输入,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/27332409/