擅长:python、mysql、java
<h2>二进制搜索的实现</h2>
<p>首先,递归是令人讨厌的。如果可以的话,请避免这种情况——如果不走运的话,它会在非常大的搜索空间中导致这类MaxRecursion错误。在</p>
<p>让我们切换到迭代,看看我们能做些什么:</p>
<pre><code>def binary_search(lst, word):
new_lst = sorted(lst) # so we only do this once
return _binary_search(new_lst, word, start=0, end=len(new_lst))
def _binary_search(lst, word, start, end):
while end - start > 0: # technically this is just while end-start but...
pivot = (start + end) // 2 # floordiv!
pivot_element = lst[pivot]
if word > pivot_element:
start = pivot + 1
elif word < pivot_element:
end = pivot
else: # word == pivot_element
return word
else: return None
>>> my_list = ['apple', 'banana', 'peach', 'pear', 'melon', 'lemon', 'grape', 'berry']
>>> print(binary_search(my_list, "strawberry"))
None
>>> print(binary_search(my_list, "pear"))
"pear"
</code></pre>