python - 检查元素是否在排序列表中的递归函数

Question

我并不是真的喜欢递归函数，我要求在递归和更优化的函数中更改我的函数。我知道在这个任务中我应该利用这个列表已排序的事实，但我不知道如何，也许是一些冒泡排序？这是我的代码，非常简单但甚至不是递归的，它不考虑列表是否已排序。

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

Answer 1

你可以做的是使用分而治之，这意味着:
算法是这样的:
你有一个总共 n 个元素的排序列表。如果 n/2 处的元素是您要查找的元素，则 checkin 数组
如果不是，作为一个排序列表，你知道 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)