バイナリサーチアルゴリズムのPythonコードがコンパイルされない

Question

バイナリサーチアルゴリズムをPythonで実装しようとしています。 私の電話でこのコードを書いたが、コンパイルしなかった。 それはなぜコンパイルされないのかわかりません。 （私はコンピュータ上でそれを試していません。）

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

コンパイルからこのコードを保持しますか？ 私の間違いは何ですか？どうすれば修正できますか？

Answer 1

まず、コードが自分のマシンで正常に動作しています。第二に、あなたのロジックに欠陥があります。 resは、親関数とは異なるスコープにあるため、BinarySearch()関数では決して割り当てられません。また、基本ケースチェックは、firstまたはsecondで行うべきではありません。機能の冒頭でsortedListに行う必要があります。また、値がDivideSearch()関数で見つかった場合は、チェックすることもできます。 HTTPあなたはPythonのインデントについて学ぶ必要があります,,,,私は!!!あなたはそれがあなたの質問にあなたを与えるエラーが含まれている必要があり、この

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