二进制搜索功能

晚上好。我正试图回到编程，并决定在我自己的时间做一些练习编码。我目前正在尝试实现二进制搜索，但似乎在我的代码中有一个连续的循环。有人能给我一个关于发生了什么的暗示吗？二进制搜索功能

def binChop(key, ordered_set): 

    found = False 
    newSet = ordered_set 

    while found != True or newSet > 0: 
     midpoint = int(len(newSet)/2) 
     if key < newSet[midpoint]: 
      found = False 
      newSet = newSet[:midpoint] 
     elif key > newSet[midpoint]: 
      found = False 
      newSet = newSet[midpoint:] 
     elif key==newSet[midpoint]: 
      found = True 
    return found

来源

2012-10-31 Cipher

还有，如果集被减少为单个元件（或零种元素）没有有效的退出条件和检索关键字是未找到。（*编辑*：除非'newSet> 0'确实检查'len（newSet）> 0';'ordered_set'的类型是什么？） – mgibsonbr

这是我完成的不同编辑的错误。感谢您的追捕，但它仍然在一个无休止的循环处：（ – Cipher

我认为你的问题是在while循环的条件。你有'或'而不是'和' - 这意味着即使你找到你的结果，newSet> 0条件也会得到满足。

来源

2012-10-31 22:11:17 Matt

这似乎工作。不幸的是我不能让它返回False，如果一个数字不在集合中，只是循环，这应该缩小为我感谢你的帮助。 – Cipher

我怀疑“newSet> 0”总是如此。如果这是一个标准的Python集，你会得到一个错误：

>>> b=set() 
>>> b 
set([]) 
>>> b > 0 
Traceback (most recent call last): 
    File "<stdin>", line 1, in <module> 
TypeError: can only compare to a set

但既然你不这样做，我想这是一个列表或元组：

>>> a=[] 
>>> a > 0 
True 
>>> b=() 
>>> b > 0 
True

哪个都没有做什么你期望（检查长度）。

一般来说，将import pdb; pdb.set_trace()添加到代码中并逐步找出错误。

来源

2012-10-31 22:12:57 lynxlynxlynx

太棒了。感谢你的领导。这会派上用场 – Cipher

您有可以改进的几个问题和一些：

您需要的左右边界指标正确执行二进制搜索时，该元素是不是在有序列表。请参阅正确的算法here。当您找到您的钥匙或左侧边界位于右侧边界右侧时，您可以离开while循环（max_point < min_point）。
您不需要newSet。您始终可以在排序列表中使用索引。所以mid_point只是一个索引，min_point（左边界）和max_point（右边界）也是如此。
二分搜索通常返回键的索引作为返回。如果没有找到，请返回-1。

我的Python代码如下所示：

def binChop(key, ordered_list): 

    min_point, max_point = 0, len(ordered_list)-1 

    while min_point <= max_point: 
     mid_point = (min_point+max_point)/2 

     if ordered_list[mid_point] < key: 
      min_point += 1 
     elif ordered_list[mid_point] > key: 
      max_point -= 1 
     else: 
      return mid_point 
    return -1 

test_cases = [[], [5], [4,5], [5,6], [1,5,6], [1], [1,4], [1,6,15]] 
for ordered_list in test_cases: 
    print "%-10s %5s" % (ordered_list, binChop(5, ordered_list))

Outputs: 
list  index of 5 
[]   -1 
[5]   0 
[4, 5]   1 
[5, 6]   0 
[1, 5, 6]  1 
[1]   -1 
[1, 4]  -1 
[1, 6, 15] -1

来源

2012-11-01 05:47:24 greeness

二进制搜索功能

回答

相关问题