Une fonction récursive pour vérifier si l'élément est dans la liste TRIÉ

Nov 27 2020

Je ne suis pas vraiment dans la fonction récursive et je demande de changer ma fonction en fonction récursive et plus optimale. Je sais que dans cette tâche, je devrais profiter du fait que cette liste est triée, mais je ne sais pas comment, peut-être une sorte de bulle? C'est mon code, assez simple mais même pas récursif et il ne prend pas en compte si la liste est triée ou non.

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

Réponses

2 Denis Nov 27 2020 at 21:52

ce que vous pourriez faire, c'est utiliser devide and conquer, ce qui signifie:

L'algo va comme ceci:

Vous avez une liste triée de n éléments au total. Checkin array si l'élément en n / 2 est celui que vous recherchez Si ce n'est pas le cas, étant une liste triée, vous savez que tous les éléments de n / 2 -> n sont plus grands, et tous les éléments de 0 -> n / 2 sont plus petits. Vérifiez si le nombre à n / 2 est inférieur ou supérieur à celui que vous recherchez. Si c'est moins, vous exécutez à nouveau la même fonction, mais maintenant, vous ne lui donnez qu'un sous-ensemble de la liste, ce qui signifie que s'il est plus petit, vous donnez 0 -> n / 2, s'il est plus grand, vous donnez n / 2 -> n . Bien sûr, vous aurez besoin de quelques conditions d'arrêt mais bon, c'est l'algo.

C'est la théorie, voici le code.

Pas la meilleure mise en œuvre de celui-ci, juste du haut de mon esprit.

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)