在Python中實現修改的二進制搜索

-2

問題是要找到小於或等於N的元素的索引。爲了解決這個問題，我編寫了下面的代碼，但它似乎不工作。在Python中實現修改的二進制搜索

def find_index(primes, N, start, end): 
    mid = int((start + end)/2) 
    if start == end: 
    return start 

    if primes[mid - 1] < N: 
     if primes[mid] == N: 
      return mid 
     elif primes[mid] > N: 
      return mid - 1 
     else: 
      return find_index(primes, N, start, mid + 1) 
    elif primes[mid - 1] > N: 
     if primes[mid] > N: 
      return find_index(primes, N, mid - 1, end)

我缺少什麼明顯的病情？有沒有更好的方法來找到O（log（n））中的索引？

來源

2014-11-25 Manu

在python中有一個bisect。所以如果你沒有在教育目的上這樣做，那就使用它。如果在教育中 - 顯示你如何調試你的腳本。 – 2014-11-25 09:53:31

請比*更精確「似乎不工作」*。 – jonrsharpe 2014-11-25 10:02:59

@SalvadorDali，我將其用於教育目的，並感謝您的建議。我會盡力找到Bisect模塊的工作。 – Manu 2014-11-25 11:16:16

如果你有大小2或更大，分而治之的列表：

def find_index(primes, N, start, end): 
    mid = int((start + end)/2) 

    if start == end: 
     return start 

    if end - start == 1: 
     return end if primes[end] < N else start 

    if primes[mid] == N: 
     return mid 
    elif primes[mid] < N: 
     return find_index(primes, N, mid, end) 
    else: 
     return find_index(primes, N, start, mid)

的邏輯在這裏在於通過中點選擇子表將最終產生start和1end之間的差異。由於以下原因可以假設：

由於(start + end)/2 = floor((start + end)/2)，中點最終將離開上邊界1個索引。
大小爲2的列表（例如開始/結束3/4或2/3）將總是產生大小爲2的列表，因爲中點將是下限。這是顯而易見的(n + n + 1)/2 = (2n + 1)/2 => 2n/2 = n。

一旦達到1的差異，可以檢查頂部和底部是否滿足less than N的要求。

未處理完全空白列表案例。

來源

2014-11-25 11:30:49 abeaamase

在Python中實現修改的二進制搜索

回答

相關問題