python - 二进制搜索功能，取决于偶数和奇数输入

我有此功能f(n) = x使用二进制搜索来查找可能不存在的x。麻烦的是，f(n)区分偶数和奇数，从而保证了f(x) < f(x+2)，但不能保证。

有限列表示例：

x = [0,1,1,2,3,5,4,7,6,8,13]

x[5] < x[7] but f[5] > f[6]

目前，我执行两个单独的binarySearches，一个用于偶数，一个用于上数：

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

    ...

但是确保f(x) < f(x+1)是偶数还是奇数会使我遇到停止问题，并产生了StackOverflows。我在哪里以及如何确保不会发生这种情况？

奖励：如何在不使用两个单独的binarySearches的情况下解决此问题？

最佳答案

如果阵列不是那么大，则意味着可以使用额外的存储空间。我建议您在二进制搜索之前将数组分开，因为这样做会使问题更容易解决。

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/