要素がSORTEDリストにあるかどうかをチェックする再帰関数

Nov 27 2020

私は実際には再帰関数に興味がなく、再帰的でより最適な関数で関数を変更するように求めています。このタスクでは、このリストがソートされているという事実を利用する必要があることを知っていますが、方法がわかりません。おそらくバブルソートですか?これは私のコードで、非常に単純ですが再帰的ではなく、リストがソートされているかどうかは考慮されていません。

list1 = [1, 2, 3, 4, 5, 6]


def is_in_List(x):
    if x in list1:
        return True
    else:
        return False


x = 3

if is_in_List(x):
    print(f"{x} is in list")
else:
    print(f"{x} is not in list")

回答

2 Denis Nov 27 2020 at 21:52

あなたができることは、分割統治法を使用することです。これは、次のことを意味します。

アルゴは次のようになります:

合計n個の要素のソート済みリストがあります。n / 2の要素が探している要素であるかどうかを配列にチェックインします。そうでない場合は、並べ替えられたリストであるため、n / 2-> nのすべての要素が大きく、0のすべての要素が大きいことがわかります。 -> n / 2は小さいです。n / 2の数値が、検索している数値よりも少ないか多いかを確認してください。それより少ない場合は、同じ関数を再度実行しますが、ここでは、リストのサブセットのみを指定します。つまり、小さい場合は0-> n / 2を指定し、大きい場合はn / 2-> nを指定します。 。もちろん、いくつかの停止条件が必要になりますが、ねえ、これはアルゴです。

それが理論です、ここにコードがあります。

私の頭のてっぺんから、それの最良の実装ではありません。

my_list = [1,2,3,4,5,6,7,8,9];


def binary_search(a_list, search_term):

    #get the middle position of the array and convert it to int    
    middle_pos = int((len(a_list)-1)/2)
    
    #check if the array has only one element, and if so it it is not equal to what we're searching for, than nothing is in the aray
    
    if len(a_list) == 1 and search_term != a_list[middle_pos] :
        #means there are no more elements to search through
        return False
    
    #get the middle term of the list
    middle_term = a_list[middle_pos]
    
    #check if they are equal, if so, the number is in the array
    if search_term == middle_term:
        return True
    
    #if the middle is less than search, it means we need to search in the list from middle to top
    if middle_term < search_term : 
        #run the same algo, but now on a subset of the given list
        return binary_search(a_list[middle_pos:len(a_list)], search_term)
        
    else : 
        #on else, it means its less, we need to search from 0 to middle
        #run the same algo, but now on a subset of the given list
        return binary_search(a_list[0:middle_pos], search_term)
        
print(binary_search(my_list, 1)