Wie führe ich eine binäre Suche nach Wörtern durch, die mit einem bestimmten Buchstaben beginnen?

Question

Ich bin aufgefordert, binäre Suche nach einer Liste von Namen und wenn diese Namen mit einem bestimmten Buchstaben beginnen, zum Beispiel A, dann soll ich diesen Namen drucken. Ich kann diese Aufgabe abschließen, indem viel einfacher Code zu tun wie

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

sondern ich gefragt werde, eine binäre Suche zu verwenden, und ich kämpfen, um den Prozess dahinter zu verstehen. Wir erhalten einen Basiscode, der die Position einer gegebenen Zeichenfolge ausgeben kann. Mein Problem ist nicht zu wissen, was so zu bearbeiten, dass ich das gewünschte Ergebnis

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.") 

Gewünschtes Ergebnis erzielen können

bin_search(name_list,"A") 

Drucke alle Namen beginnend mit A (Adolphus von HelBorne, Aldric Foxe .... usw.)

EDIT: Ich war nur etwas raten und überprüfen und herausgefunden, wie es geht. Dies ist die Lösung Code

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) 

Answer 1

nicht sicher, ob dies ist, was Sie wollen, da es ineffizient scheint ... wie Sie erwähnen es viel intuitiver scheint über die gesamte Liste nur zu wiederholen, sondern binäre Suche i gefunden here ich habe:

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] 

Output i erhalten:

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

Answer 2

Sie müssen nur ein Einzelteil gefunden beginnt mit dem Buchstaben, dann müssen Sie den Bereich identifizieren. Dieser Ansatz sollte schnell und speichereffizient sein.

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.") 

die Ausgabe

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