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

Question

我有这个功能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] 

目前我做两个不同的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 

    ... 

但确保mid是偶数或奇数给我停止的问题和我产生StackOverflows。我在哪里以及如何确保这不会发生？

奖励：如何解决这个问题，而不使用两个单独的binarySearches？

Answer 1

如果数组不大，这意味着额外的内存空间是可接受的。我建议你在二进制搜索之前分开数组，因为这会让问题变得更容易。你可以直接使用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) 

注意上意味着这里最后一个元素的index但不index+1。如果这不是你的情况，需要做一些小的改动。

实际上，与普通二分查找没有多大区别。对于正常情况，边缘情况是具有0,1或2个元素的数组，而在这里它变为0,1或3.