在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中实现修改的二进制搜索

回答

相关问题