python - 检查元素是否在排序列表中的递归函数
问题描述
我并没有真正进入递归函数,我要求以递归和更优化的函数更改我的函数。我知道在这个任务中我应该利用这个列表排序的事实,但我不知道如何,也许是一些冒泡排序?这是我的代码,非常简单,但甚至不是递归的,它没有考虑列表是否排序。
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")
解决方案
您可以做的是使用分而治之,这意味着:
算法是这样的:
您有一个包含 n 个元素的排序列表。如果 n/2 处的元素是您要查找的元素,则检查数组如果不是,作为排序列表,您知道 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)
推荐阅读
- php - 在 php 中通过 openssl_encrypt 和 openssl_decrypt 使用 openssl 会出错
- javascript - 通过单击按钮打开模式并通过单击关闭按钮隐藏模式
- html - CSS 悬停过渡
- java - __builtin_clz 的 Java 等价物是什么?
- aws-cdk - aws cdk 使用非默认配置文件
- python - 什么是 django.db.utils.OperationalError: (2000, 'Unknown MySQL error')
- kubernetes - Kubernetes 并行计算
- javascript - Javascript:解析每个 CSV 列以分隔 JSON
- php - Array_intersect 和返回值的顺序
- java - Spring安全认证服务器