在Python排序的名称列表中线性搜索名称

Question

考虑以下不完整函数：

def linear_search_sorted(names, search_name):
for name in names:
...
return False

上述函数以排序名称列表和目标名称作为参数，并在参数排序列表中搜索给定名称。如果列表中存在搜索值，则函数返回True，否则返回False。完成上面的函数，这样它还可以返回搜索给定名称所需的元素总数和相等比较总数(即使用==(。

def linear_search_sorted(names, search_name):
length = len(names)
comp = 0
for name in names:
comp += 1
if name == search_name: 
return (True, length,comp)

elif name[0] == search_name[0]:
return (False, length, comp)
return (False,length, comp)

测试1:

result = linear_search_sorted(['Abby', 'Bella', 'Charlotte', 'Daisy', 'Ella', 'Faith', 'Grace', 'Hannah'], 'Bella')
print('Found: {} Length: {} Comparisons: {}'.format(result[0], result[1], result[2]))

输出1:

Expected ->   Found: True Length: 8 Comparisons: 2
Got ->        Found: True Length: 8 Comparisons: 2

测试2:

result = linear_search_sorted(['Abby', 'Bella', 'Charlotte', 'Daisy', 'Ella', 'Faith', 'Grace', 'Hannah'], 'Natalie')
print('Found: {} Length: {} Comparisons: {}'.format(result[0], result[1], result[2]))

输出2:

Expected ->    Found: False Length: 8 Comparisons: 8
Got ->         Found: False Length: 8 Comparisons: 8

测试3:

result = linear_search_sorted(['Abby', 'Bella', 'Charlotte', 'Daisy', 'Ella', 'Faith', 'Grace', 'Hannah', 'Isabella', 'Jade', 'Kate', 'Lily', 'Maddison', 'Natalie', 'Olivia', 'Phoebe', 'Queen', 'Rebecca', 'Samantha'], 'Ethan')
print('Found: {} Length: {} Comparisons: {}'.format(result[0], result[1], result[2]))

输出3:

Expected ->    Found: False Length: 19 Comparisons: 6
Got ->         Found: False Length: 19 Comparisons: 5

我知道对于Test3，search_name是"Ethan"，所以函数的工作方式应该与"Faith"相比较，因为列表是排序的，在Faith之后，找不到Ethan(以E开头(。但我不知道我该如何将我的比较上升到那个地步。有人能帮忙吗。

Answer 1

我认为这段代码的目的应该检查第一个字母是否大于而不是等于搜索到的名称。

因此：

def linear_search_sorted(names, search_name):
length = len(names)
comp = 0
for name in names:
comp += 1
if name == search_name: 
return (True, length,comp)

elif name[0] > search_name[0]:
return (False, length, comp)
return (False,length, comp)

这将返回您的所有预期结果。

Answer 2

您为输入列表中的每个名称递增comp。只有在测试相等性时，才应该递增它。

def linear_search_sorted(names, search_name):
count = 0
for name in names:
if name > search_name:
break
count += 1
if name == search_name:
return True, len(names), count
return False, len(names), count

print(linear_search_sorted(['Abby', 'Bella', 'Charlotte', 'Daisy', 'Ella', 'Faith', 'Grace', 'Hannah', 'Isabella', 'Jade', 'Kate', 'Lily', 'Maddison', 'Natalie', 'Olivia', 'Phoebe', 'Queen', 'Rebecca', 'Samantha'], 'Ethan'))

所以输出应该是：

(False, 19, 5)

因为我们测试了5次相等性(Abby->Ella(。一旦我们到达Faith，我们就知道由于词法>比较