a=3
b=-2
x=(a+b)/2.0 # 中点
def f(x): # 定义方程式
y=x-2**0.5
return(y)
u=max([a,b])
l=min([a,b])
i=0
z=[]
est=[]
# 循环体
while abs(f(x))>10.0**(-15.0): # 计算精度
if f(u)*f(l)>0: # 判断输入假设是否成立
print('Error: Assumption not holds! ')
break
if f(x)*f(u)>0: # 判断零点落入区间
u=x
x=(x+l)/2.0
else:
l=x
x=(x+u)/2.0
i=i+1
z=z+[abs(x-2**0.5)]
est=est+[abs(a-b)/2**i]
plt.semilogy(z)
plt.semilogy(est)
plt.grid('on')
plt.legend(['simu','theo'])
plt.show()
1 引言
有序序列元素查找是python算法中典型且重要的技能,通过对有序序列元素查找的学习,我们可以更快的解决关于有序序列查找的相关问题,也可以更好的体现出我们的解题思维逻辑能力和提高代码水平。
查找元素。一般地,我们可以用for循环进行遍历,再用if语句进行查找。相对于for循环,二分法更加方便。二分法思想 对于已按照关键字排序的序列,经过一次比较后,可将序列分割成两部分,然后只在有可能包含待查找元素的一部分中继续查找,并根据试探结果继续分割,逐步缩小查找范围,直至找到或找不到为止。
2 问题描述
示例:如何查找有序序列中某一的元素
输入:[1,2,3,4,5,6,……,100] 61 #查找的元素
输出:61
3 算法描述
在这里我们主要使用二分法查找。二分法主要是与给定的一列序数中的中位数进行比较,然后再选取范围进行查找。如在[1,2,3,4,……,100]中查找61。先取1—100之间的中位数50进行比较,因为50比61小,所以排除1—50之间的数,再用51—100之间的中位数75进行比较,因为75大于61‘所以排除75—100的元素。然后反复地用这个方法排除多余的元素,直到剩下需要查找的元素(61)。
4 结语
有序序列中元素的查找有两种方法:一是用for循环进行遍历查找。二是二分法进行查找。对于会执行很多次的查找时采用二分法比较方便。
附件
def my_func(my_list, searched_number): #二分法
start_number_index = 0
end_number_index = len(my_list) - 1
while start_number_index <= end_number_index:
mid_number_index = (start_number_index = end_number_index) // 2
mid_number = my_list[mid_number_index]
if mid_number <searched_number:
start_number_index = mid_number_indexn+ 1
elif mid_number >searched_number:
end_number_index = mid_number_index - 1
else:
return '找到了需要查找的数字%d'% searched_number
my_list = list(range(1,101))
searched_number = 61
print(my_func(my_list, mid_number))# 结果 找到了需要查找的数字 61
因为他已经把middle位置上的数字已经检查过了,第一个if条件就是判断middle位置山的数字是不是想要的,既然这个条件不满足,那么就肯定不需要他,所以从他的上一位或下一位重新开始