二進制搜索功能，取決於偶數和奇數輸入

我有這個功能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？

來源

2014-12-06 Sven

'x [5] x [6]'，當然。 – 2014-12-06 13:56:24

'（mid // 2）* 2'怎麼樣？ – Wolph 2014-12-06 14:03:07

如果數組不大，這意味着額外的內存空間是可接受的。我建議你在二進制搜索之前分開數組，因爲這會讓問題變得更容易。你可以直接使用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.

來源

2014-12-06 15:02:08 owenwater

二進制搜索功能，取決於偶數和奇數輸入

回答

相關問題