<p>似乎,根据你的代码,二进制搜索有一个概念上的问题。如果我们先解决这个问题,代码应该更有意义。你知道吗</p>
<p><strong>什么是二进制搜索?</strong></p>
<p>给定一个有序的列表和一个您正在搜索的项目,您将列表减半,然后依次查看每一半。让我们用一个例子来看看这个。给定<code>[1, 2, 3, 4, 5, 6]</code>并搜索<code>5</code>,您将看到列表的两部分<code>[1,2,3]</code>和<code>[4,5,6]</code>。查看前半部分(<code>[1,2,3]</code>),您注意到最大的项是<code>3</code>。假设列表是有序的,那么列表中的所有项都必须小于<code>3</code>。这意味着<code>5</code>(您正在搜索的内容)不可能在较小的列表中。现在来看(<code>[4,5,6]</code>)。让我们把它分成两个列表<code>[4]</code>和<code>[5,6]</code>,依此类推。你知道吗</p>
<p><strong>如何将二进制搜索应用于我的问题</strong></p>
<p>给定一个数字列表和一个搜索项,您需要返回列表中最大的项目,该项目仍然小于搜索项。你知道吗</p>
<p>将列表分成两等分(尽可能等分,奇数大小的列表总是不均匀的)。看下半部分列表中最小的一项。如果最小的项大于搜索项,那么您就知道您要查找的值在前半个列表中。否则,它就在下半部分列表中。继续把清单分开,直到你得到你需要的东西。你知道吗</p>
<p><strong>代码是什么样子的</p>
<pre><code>def largest_item_less_than_x(x, list_of_vals):
size = len(list_of_vals)
if (size == 0):
return None
if (size == 1):
if (list_of_vals[1] < x):
return list_of_vals[1]
else:
return None
else:
mid = size // 2
left_half_list = list_of_vals[0:mid]
right_half_list = list_of_vals[mid:]
if (right_half_list[0] < x):
return largest_item_less_than_x(x, right_half_list)
else:
return largest_item_less_than_x(x, left_half_list)
</code></pre>
<p>让我们浏览一下代码。如果你给它一个空列表,它将返回无。也就是说,如果没有可供选择的元素,搜索一个项将不会返回任何结果。你知道吗</p>
<p>如果你给它一个单一的列表,它的值大于你要搜索的值,它将返回None,即给定<code>[6]</code>和搜索<code>3</code>,那么你将无法找到你要找的。你知道吗</p>
<p>如果你给它一个列表,它的值比你要搜索的要小,它就会返回这个值。你知道吗</p>
<p>如果给它一个包含多个项目的列表,那么它会将列表分成两半,并递归地搜索每一半。你知道吗</p>
<p>希望这有道理。你知道吗</p>