Una función recursiva para verificar si el elemento está en la lista CLASIFICADA

Nov 27 2020

Realmente no estoy en la función recursiva y estoy pidiendo cambiar mi función en una función recursiva y más óptima. Sé que en esta tarea debo aprovechar que esta lista está ordenada, pero no sé cómo, ¿tal vez algún tipo de burbuja? Este es mi código, bastante simple pero ni siquiera recursivo y no tiene en cuenta si la lista está ordenada o no.

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

Respuestas

2 Denis Nov 27 2020 at 21:52

lo que podría hacer es usar dividir y conquistar, lo que significa:

El algoritmo es así:

Tiene una lista ordenada de n elementos totales. Verificar matriz si el elemento en n / 2 es el que está buscando Si no lo es, al ser una lista ordenada, sabe que todos los elementos de n / 2 -> n son más grandes y todos los elementos de 0 -> n / 2 son más pequeños. Compruebe si el número en n / 2 es menor o mayor que el que está buscando. Si es menor, ejecuta la misma función nuevamente, pero ahora, le da solo un subconjunto de la lista, es decir, si es más pequeño le da 0 -> n / 2, si es más grande, le da n / 2 -> n . Por supuesto, necesitará algunas condiciones de parada, pero bueno, este es el algoritmo.

Esa es la teoría, aquí está el código.

No es la mejor implementación, solo desde lo más alto de mi mente.

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)