无法正确比较二进制搜索与线性搜索

Question

def linear_search(a_list, key):
steps = 0
for i, item in enumerate(a_list):
steps += 1
if item == key:
break
return steps

def binary_search(a_list, key):
a_list.sort()
steps = 1
left = 0
right = len(a_list) - 1
while left <= right:
steps += 1
middle = (left + right) // 2
if a_list[middle] == key:
break
if a_list[middle] > key:
right = middle - 1
if a_list[middle] < key:
left = middle + 1
return steps

def best_search(a_list, key):
steps_linear = linear_search(a_list, key)
steps_binary = binary_search(a_list, key)
results = "Linear: " + str(steps_linear) + " steps, "
results += "Binary: " + str(steps_binary) + " steps. "
if linear_search(a_list, key) < binary_search(a_list, key):
results += "Best Search is Linear."
elif binary_search(a_list, key) < linear_search(a_list, key):
results += "Best Search is Binary."
else:
results += "Result is a Tie."
return results

测试

print(best_search([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 1))
print(best_search([10, 2, 9, 1, 7, 5, 3, 4, 6, 8], 1))
print(best_search([10, 9, 8, 7, 6, 5, 4, 3, 2, 1], 7))
print(best_search([1, 3, 5, 7, 9, 10, 2, 4, 6, 8], 10))
print(best_search([5, 1, 8, 2, 4, 10, 7, 6, 3, 9], 11))

我已经调试了这段代码，但无法弄清楚为什么它不会绑定。它确实正确计算了步骤，但不能正确决定哪个更好。

Answer 1

所以你的代码有几个问题：

1. 正如@Samwise所说，您没有在best_search中调用搜索函数。应该更新：

   steps_linear = linear_search(a_list, key)
   steps_binary = binary_search(a_list, key)
   ...
   

2. 但是，一旦你这样做了，运行代码后会出现另一个问题：

   Linear: -1 steps, Binary: 0 steps. Best Search is Linear.
   Linear: -1 steps, Binary: 0 steps. Best Search is Linear.
   Linear: -1 steps, Binary: 6 steps. Best Search is Linear.
   Linear: -1 steps, Binary: 9 steps. Best Search is Linear.
   Linear: -1 steps, Binary: -1 steps. Result is a Tie.
   

   这些显然不是所需的输出。为什么linear_search总是返回 -1？它总是返回 -1，因为这是您指定它始终返回的内容：

   def linear_search(a_list, key):
   # Returns the number of steps to determine if key is in the list
   # Initialize the counter of steps
   steps = 0
   for i, item in enumerate(a_list):
   steps += 1
   if item == key:
   break
   return -1 # <--- this is your only return statement!!
   

   但是您希望返回执行搜索所需的步骤数，因此请返回该步骤数。当你找到键时，不要中断循环，而只是返回它，因为返回步骤将结束函数：

   if item == key:
   return steps
   

   输出：

   Linear: 1 steps, Binary: 0 steps. Best Search is Binary.
   Linear: 4 steps, Binary: 0 steps. Best Search is Binary.
   Linear: 4 steps, Binary: 6 steps. Best Search is Linear.
   Linear: 6 steps, Binary: 9 steps. Best Search is Linear.
   Linear: -1 steps, Binary: -1 steps. Result is a Tie.
   

   已经看起来更好了.linear_search返回除最后一个测试之外的所有测试的所需输出，我将在后面介绍。

3. 但是，函数binary_steps没有返回所需的输出。为什么？好吧，对于初学者来说，您实际上永远不会返回steps：

   def binary_search(a_list, key):
   # Returns the number of steps to determine if key is in the list
   # List must be sorted:
   a_list.sort()
   # The Sort was 1 step, so initialize the counter of steps to 1
   steps = 1
   left = 0
   right = len(a_list) - 1
   while left <= right:
   middle = (left + right) // 2
   if a_list[middle] == key:
   return middle # you return `middle`
   if a_list[middle] > key:
   right = middle - 1
   if a_list[middle] < key:
   left = middle + 1
   return -1 # or -1, but not `steps`
   

   相反，当找到匹配项时，您将返回middle。因此，请将其替换为return steps：

   if a_list[middle] == key:
   return steps
   

   但是现在你得到这个：

   Linear: 1 steps, Binary: 1 steps. Result is a Tie.
   Linear: 4 steps, Binary: 1 steps. Best Search is Binary.
   Linear: 4 steps, Binary: 1 steps. Best Search is Binary.
   Linear: 6 steps, Binary: 1 steps. Best Search is Binary.
   Linear: -1 steps, Binary: -1 steps. Result is a Tie.
   

   这仍然不是您想要的输出。为什么binary_search不返回所需的输出？因为您不会为循环的每次迭代递增steps，所以steps将始终为 1！每次循环迭代时递增steps：

   while left <= right:
   steps += 1
   middle = (left + right) // 2
   ...
   

   。看看我们得到了什么：

   Linear: 1 steps, Binary: 4 steps. Best Search is Linear.
   Linear: 4 steps, Binary: 4 steps. Result is a Tie.
   Linear: 4 steps, Binary: 5 steps. Best Search is Linear.
   Linear: 6 steps, Binary: 5 steps. Best Search is Binary.
   Linear: -1 steps, Binary: -1 steps. Result is a Tie.
   

4. 除最后一个测试外的所有测试都会返回所需的输出。但是最后一个测试是怎么回事呢？让我们来看看：

   print(best_search([5, 1, 8, 2, 4, 10, 7, 6, 3, 9], 11))
   # Should be: Linear: 10 steps, Binary: 5 steps. Best Search is Binary.
   

   好吧，很明显，如果没有 11，您将无法在列表中找到 11，因此您永远无法在此处获得所需的输出。您要么必须更改键，要么修改输入列表和 11

   。

这是最终代码：

def linear_search(a_list, key):
# Returns the number of steps to determine if key is in the list
# Initialize the counter of steps
steps = 0
for i, item in enumerate(a_list):
steps += 1
if item == key:
return steps
return -1

def binary_search(a_list, key):
# Returns the number of steps to determine if key is in the list
# List must be sorted:
a_list.sort()
# The Sort was 1 step, so initialize the counter of steps to 1
steps = 1
left = 0
right = len(a_list) - 1
while left <= right:
steps += 1
middle = (left + right) // 2
if a_list[middle] == key:
return steps
if a_list[middle] > key:
right = middle - 1
if a_list[middle] < key:
left = middle + 1
return -1

def best_search(a_list, key):
steps_linear = linear_search(a_list, key)
steps_binary = binary_search(a_list, key)
results = "Linear: " + str(steps_linear) + " steps, "
results += "Binary: " + str(steps_binary) + " steps. "
if steps_linear < steps_binary:
results += "Best Search is Linear."
elif steps_binary < steps_linear:
results += "Best Search is Binary."
else:
results += "Result is a Tie."
return results
print(best_search([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 1))
# Should be: Linear: 1 steps, Binary: 4 steps. Best Search is Linear.
print(best_search([10, 2, 9, 1, 7, 5, 3, 4, 6, 8], 1))
# Should be: Linear: 4 steps, Binary: 4 steps. Result is a Tie.
print(best_search([10, 9, 8, 7, 6, 5, 4, 3, 2, 1], 7))
# Should be: Linear: 4 steps, Binary: 5 steps. Best Search is Linear.
print(best_search([1, 3, 5, 7, 9, 10, 2, 4, 6, 8], 10))
# Should be: Linear: 6 steps, Binary: 5 steps. Best Search is Binary.
print(best_search([5, 1, 8, 2, 4, 10, 7, 6, 3, 9], 11))
# Should be: Linear: 10 steps, Binary: 5 steps. Best Search is Binary.

在线运行和编辑此代码

这现在应该适合您。

---

至于你的另一个问题(编辑问题后看到)，问题是你有以下几行：

steps_linear = linear_search(a_list, key)
steps_binary = binary_search(a_list, key)

。在best_search中，但您再次调用linear_search并best_search进行比较：

if linear_search(a_list, key) < binary_search(a_list, key):
results += "Best Search is Linear."
elif binary_search(a_list, key) < linear_search(a_list, key):
results += "Best Search is Binary."

这不仅不需要，而且实际上会搞砸测试。如果你看一下a_list，因为它在best_search的过程中，你会注意到一些东西：

a_list, before calling any searches: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
a_list, after calling all searches: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Linear: 1 steps, Binary: 4 steps. Best Search is Linear. 

a_list, before calling any searches: [10, 2, 9, 1, 7, 5, 3, 4, 6, 8]
a_list, after calling all searches: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Linear: 4 steps, Binary: 4 steps. Best Search is Linear. 

a_list, before calling any searches: [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
a_list, after calling all searches: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Linear: 4 steps, Binary: 5 steps. Best Search is Binary. 

a_list, before calling any searches: [1, 3, 5, 7, 9, 10, 2, 4, 6, 8]
a_list, after calling all searches: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Linear: 6 steps, Binary: 5 steps. Best Search is Binary. 

a_list, before calling any searches: [5, 1, 8, 2, 4, 10, 7, 6, 3, 9]
a_list, after calling all searches: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Linear: -1 steps, Binary: -1 steps. Result is a Tie. 

每次搜索后，a_list最终都会排序。为什么？因为每当你调用binary_search，这是运行的第一件事：

a_list.sort()

Python 的.sort()修改列表本身;它不会返回新列表。因此，让我们再次看一下best_search(注意评论)：

def best_search(a_list, key):
steps_linear = linear_search(a_list, key)
steps_binary = binary_search(a_list, key) # <-- you call binary_search for the first time, so a_list is sorted
results = "Linear: " + str(steps_linear) + " steps, "
results += "Binary: " + str(steps_binary) + " steps. "
if linear_search(a_list, key) < binary_search(a_list, key): # <-- you call linear_serch and binary_search with the sorted list
results += "Best Search is Linear."
elif binary_search(a_list, key) < linear_search(a_list, key):
results += "Best Search is Binary."
else:
results += "Result is a Tie."
return results

所以基本上你的测试最终是相同的，因为你每次都在搜索之前对列表进行排序。要解决此问题，只需将steps_linear与steps_binary进行比较，而无需再次调用函数;这是多余的。这样：

def best_search(a_list, key):
steps_linear = linear_search(a_list, key)
steps_binary = binary_search(a_list, key)
results = "Linear: " + str(steps_linear) + " steps, "
results += "Binary: " + str(steps_binary) + " steps. "
if steps_linear < steps_binary:
results += "Best Search is Linear."
elif steps_binary < steps_linear:
results += "Best Search is Binary."
else:
results += "Result is a Tie."
return results

输出：

Linear: 1 steps, Binary: 4 steps. Best Search is Linear.
Linear: 4 steps, Binary: 4 steps. Result is a Tie.
Linear: 4 steps, Binary: 5 steps. Best Search is Linear.
Linear: 6 steps, Binary: 5 steps. Best Search is Binary.
Linear: -1 steps, Binary: -1 steps. Result is a Tie.

在线运行和编辑此代码

现在比较有效。

Answer 2

尽管这些答案是正确的，但在我用return steps替换return -1之前，它并没有为我运行。将return -1替换为return steps，它不会每次都显示相同的答案。

Answer 3

修复以下内容

线性：-1 步，二进制：-1 步。结果是平局。

我们需要将"return -1"替换为"return steps">