Eine rekursive Funktion, um zu überprüfen, ob sich das Element in der Liste SORTIERT befindet

Nov 27 2020

Ich bin nicht wirklich in rekursive Funktion und ich bitte, meine Funktion in rekursiven und optimaleren Funktionen zu ändern. Ich weiß, dass ich bei dieser Aufgabe die Tatsache ausnutzen sollte, dass diese Liste sortiert ist, aber ich weiß nicht wie, vielleicht eine Blasensortierung? Dies ist mein Code, ziemlich einfach, aber nicht einmal rekursiv, und er berücksichtigt nicht, ob die Liste sortiert ist oder nicht.

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

Antworten

2 Denis Nov 27 2020 at 21:52

Was Sie tun könnten, ist Devide und Conquer zu verwenden, was bedeutet:

Das Algo geht so:

Sie haben eine sortierte Liste von n Gesamtelementen. Check-in-Array, wenn das Element bei n / 2 das gesuchte ist Wenn dies nicht der Fall ist, wissen Sie, dass alle Elemente von n / 2 -> n größer sind und alle Elemente von 0 -> n / 2 sind kleiner. Überprüfen Sie, ob die Zahl bei n / 2 kleiner oder höher ist als die gesuchte. Wenn es kleiner ist, führen Sie dieselbe Funktion erneut aus, aber jetzt geben Sie ihr nur eine Teilmenge der Liste. Wenn sie kleiner ist, geben Sie 0 -> n / 2, wenn sie größer ist, geben Sie n / 2 -> n . Natürlich brauchen Sie einige Stoppbedingungen, aber hey, das ist der Algo.

Das ist die Theorie, hier ist der Code.

Nicht die beste Umsetzung, nur aus meiner Sicht.

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)