如何对以某个字母开头的单词执行二分查找？

我被要求对二进制搜索名称列表进行搜索，如果这些名称以特定字母开头，例如A，那么我将打印该名称。我可以做更多简单的代码，如如何对以某个字母开头的单词执行二分查找？

for i in list: 
    if i[0] == "A": 
     print(i)

完成这个任务，而是要求我使用二进制搜索，我努力理解其背后的过程。我们给出了可以输出给定字符串的位置的基本代码。我的问题是不知道该怎么修改，这样我可以达到理想的结果

name_list = ["Adolphus of Helborne", "Aldric Foxe", "Amanita Maleficant", "Aphra the Vicious", "Arachne the Gruesome", "Astarte Hellebore", "Brutus the Gruesome", "Cain of Avernus"] 


def bin_search(list, item): 
    low_b = 0 
    up_b = len(list) - 1 
    found = False 

    while low_b <= up_b and found == False: 
     midPos = ((low_b + up_b) // 2) 
     if list[midPos] < item: 
      low_b = midPos + 1 
     elif list[midPos] > item: 
      up_b = midPos - 1 
     else: 
      found = True 
    if found: 
     print("The name is at positon " + str(midPos)) 
     return midPos 
    else: 
     print("The name was not in the list.")

期望的结果

bin_search(name_list,"A")

打印所有的名字开始与HelBorne的A（阿道夫Aldric福克斯....等）

编辑：我只是做一些猜测和检查，并找到了如何做到这一点。这是解决方案代码

def bin_search(list, item): 
    low_b = 0 
    up_b = len(list) - 1 
    true_list = [] 
    count = 100 
    while low_b <= up_b and count > 0: 
     midPos = ((low_b + up_b) // 2) 
     if list[midPos][0] == item: 
      true_list.append(list[midPos]) 
      list.remove(list[midPos]) 
      count -= 1 
     elif list[midPos] < item: 
      low_b = midPos + 1 
      count -= 1 
     else: 
      up_b = midPos - 1 
      count -= 1 
    print(true_list)

来源

2016-09-27 oneman

首先，排序它 - [排序HOW TO（https://docs.python.org/3/howto/sorting.html） – wwii

抱歉，我应该有提到，我给的列表已经排序，所以我们可以跳过那部分，但是是正确的，它需要排序 – oneman

做一个二进制搜索，研究它应该如何工作，研究代码，试图找出如何它可以工作，使用打印语句来帮助*可视化*。 – wwii

不太清楚，如果这是你想要的，因为它似乎效率不高......你提到它似乎有更多直观的，只是遍历整个列表，但使用二进制搜索，我发现here我有：

def binary_search(seq, t): 
    min = 0 
    max = len(seq) - 1 
    while True: 
     if max < min: 
      return -1 
     m = (min + max) // 2 
     if seq[m][0] < t: 
      min = m + 1 
     elif seq[m][0] > t: 
      max = m - 1 
     else: 
      return m 

index=0 
while True: 
    index=binary_search(name_list,"A") 
    if index!=-1: 
     print(name_list[index]) 
    else: 
     break 
    del name_list[index]

输出I得到：

Aphra the Vicious 
Arachne the Gruesome 
Amanita Maleficant 
Astarte Hellebore 
Aldric Foxe 
Adolphus of Helborne

来源

2016-09-27 05:03:44

与线性搜索相比，二进制搜索似乎效率低下？新闻给我 –

不完全一样清楚，你把它的二进制搜索方法重复几次，因为它是在一个循环中 –

我看到你的观点，而不是想要1搜索OP想所有以A开头 –

你只需要找到一个项目开始配信，那么你需要确定的范围。这种方法应该是快速和高效的。

def binary_search(list,item): 
    low_b = 0 
    up_b = len(list) - 1 
    found = False 
    midPos = ((low_b + up_b) // 2) 
    if list[low_b][0]==item: 
     midPos=low_b 
     found=True 
    elif list[up_b][0]==item: 
     midPos = up_b 
     found=True 
    while True: 
     if found: 
      break; 
     if list[low_b][0]>item: 
      break 
     if list[up_b][0]<item: 
      break 
     if up_b<low_b: 
      break; 
     midPos = ((low_b + up_b) // 2) 
     if list[midPos][0] < item: 
      low_b = midPos + 1 
     elif list[midPos] > item: 
      up_b = midPos - 1 
     else: 
      found = True 
      break 
    if found: 
     while True: 
      if midPos>0: 
       if list[midPos][0]==item: 
        midPos=midPos-1 
        continue 
      break; 
     while True: 
      if midPos<len(list): 
       if list[midPos][0]==item: 
        print list[midPos] 
        midPos=midPos+1 
        continue 
      break 
    else: 
     print("The name was not in the list.")

输出

>>> binary_search(name_list,"A") 
Adolphus of Helborne 
Aldric Foxe 
Amanita Maleficant 
Aphra the Vicious 
Arachne the Gruesome 
Astarte Hellebore

来源

2016-09-27 11:38:31 SorMun

如何对以某个字母开头的单词执行二分查找？

回答

相关问题