A recursive function to check if element is in SORTED list

Question

I am not really into recursive function and I am asking to change my function in recursive and more optimal func. I know that in this task i should take advantage of the fact that this list is sorted, but I dont know how, maybe some bubble sort? This is my code, pretty simple but not even recursive and it doesn't take into account whether the list is sorted or not.

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

If it starts sorted, you could implement a type of binary search to find an element (https://en.wikipedia.org/wiki/Binary_search_algorithm) — Alexander L. Hayes, Nov 27 '20 at 14:33
Can you expand on why the solution *has* to be recursive? Many algorithms can be implemented in a recursive or iterative style. — Alexander L. Hayes, Nov 27 '20 at 14:37
Welcome to SO! This is a builtin: https://docs.python.org/3/library/bisect.html — ggorlen, Nov 27 '20 at 15:21
Does this answer your question? [Recursion binary search in Python](https://stackoverflow.com/questions/19989910/recursion-binary-search-in-python) — ggorlen, Nov 27 '20 at 15:22

score 2 · Answer 1 · answered Nov 27 '20 at 14:52

what you could do, is use devide and conquer, which means :

The algo goes like this :

You have a sorted list of n total elements. Checkin array if the element at n/2 is the one you're looking for If it isn't, being a sorted list, you know that all the elements from n/2 -> n are bigger, and all the elements from 0 -> n/2 are smaller. Check if the number at n/2 is less or more than the one you're searching for. If it's less, you run the same function again, but now, you give it only a subset of the list, meaning, if it's smaller you give 0 -> n/2, if it's bigger, you give n/2 -> n. Of course you'll need some stoping condtitions but hey, this is the algo.

That's the theory, here's the code.

Not the best implementation of it, just from the top of my mind.

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)

A recursive function to check if element is in SORTED list

1 Answers1