Python-Code für Binärsuchalgorithmus kompiliert nicht

Question

Ich versuche, einen binären Suchalgorithmus in Python zu implementieren. Ich schrieb diesen Code auf meinem Handy, aber es kompiliert nicht. Und ich weiß nicht, warum es nicht kompiliert. (ich habe es nicht auf einem Computer ausprobiert.)

def BinarySearch(sList, search): 
    res=0 
    sortedList=sorted(sList) 
    x=int(len(sortedList)/2) 
    mid=sortedList[x] 
    def DivideSearch(sortedList ,search): 
     first=sortedList[:mid ] 
     second=sortedList[mid:] 
     if first[len(first)-1]<search: 
      DivideSearch (first, search) 
     elif second[len(second)-1]>search: 
      DivideSearch (second, search) 
     elif len(first)==1: 
      res=first.pop() 
     elif len(second)==1: 
      res=second.pop() 
    if res==search: 
     return res 


numbers=[1,2,3,4,5,6,7,8,9] 
guess=3 

print(BinarySearch(numbers,guess)) 

Was aus der Zusammenstellung dieser Code hält? Was sind meine Fehler und wie kann ich sie beheben?

Answer 1

Zuerst läuft Ihr Code auf meinem Computer einwandfrei. Zweitens ist deine Logik fehlerhaft. res wird nie in der BinarySearch()-Funktion zugewiesen, da es sich in einem anderen Bereich als in der übergeordneten Funktion befindet. Außerdem sollte Ihre Base-Case-Prüfung nicht unter first oder second durchgeführt werden. Sie sollte am Anfang der Funktion unter sortedList durchgeführt werden. Außerdem können Sie überprüfen, ob der Wert in der DivideSearch()-Funktion gefunden wurde. Ich korrigierte Code hochzuladen, werfen Sie einen Blick auf diese

import random 
def DivideSearch(sortedList, search, mid): 
    first = sortedList[:mid] 
    second = sortedList[mid:] 
    #check for our base case 
    if len(sortedList) ==1: 
     return sortedList[0] if sortedList[0] == search else None 
    #we can immediately remove half the cases if they're less than or greater than our search value 
    #if the greatest value element in the lower half is < search value, only search the higher value list 
    if first[-1] < search: 
     #recurse 
     return DivideSearch(second, search, len(second)/2) 

    #otherwise we want to check the lower value list 
    else: 
     return DivideSearch(first, search, len(first)/2) 

def BinarySearch(sList, search): 

    sortedList=sorted(sList) 
    #determine mid cleanup 
    mid=len(sortedList)/2 
    #return the result 
    return DivideSearch(sortedList,search, mid) 



numbers=[random.randint(1, 10) for x in range(1,10)] 
guess=5 

Answer 2

def binarys(list, item): 

    #you have to keep track of the head(lo) of the list and tail(hi) 

    lo = 0 

    #a list must be sorted for binary search to work because the lower values are on the left and higher on the right 

    slist = sorted(list) 
    hi = len(slist) - 1 

    #Keep running the search as long as the start of the list is never less than or equal to the end of the list. At that point you either have 1 item left to check or the item isn't there at all. So return False 

    while lo <= hi: 
     mid = (lo + hi)//2 

     #if the item you searched for is in the middle, return True 
     if slist[mid] == item: 
     return True 

     #since it's not in the middle the first time you checked, but if the item you're looking for is less than the value of the mid item in the list then you can ignore the entire right part of the list by making the item to the left of the midpoint the new tail(hi). midpoint minus 1 because you already established the midpoint of the original list didn't have the item you searched for. 
     elif item < slist[mid]: 
     hi = mid - 1 

     # if the item you're looking for is greater than the value of the mid item in the list then you can ignore the entire left part of the list by making the item to the right of the midpoint the new head(lo). midpoint plus 1 because you already established the midpoint of the original list didn't have the item you searched for. 
     else: 
     if item > slist[mid]: 
      lo = mid+ 1 
    return False 

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