查找
查找要学习的主要内容有两个:顺序查找和二分法查找。
数据准备
import random as r
n = int(input("请输入列表元素的个数:"))
lst = []
for i in range(n):
a = r.randint(-200, 200)
while a in lst:
a = r.randint(-200, 200)
lst.append(a)
顺序查找
顺序查找也叫线性查找, 是指按一定的顺序检查列表中每一个元素,直到找到所要寻找的特定值为止。 这里需要对列表的值进行循环遍历:
def sequence_search(ls, x):
for i in ls:
if i == x:
return True
return False
if sequence_search(lst, 100):
print("100找到了。")
else:
print("没有在列表里找到100")
二分法查找
二分法查找的主要思想就是将列表进行折半查找,通过不断折半的过程来确定要查找的关键字所在的区域。
- 先将列表进行正序排序;
- 设置起始和末尾结点
start
、end
,然后得到中间结点mid
,mid = (start + end) // 2
; - 如果中间结点的值大于要查找的关键字
key
,则设置end = mid - 1
,反之,如果中间结点的值小于要查找的关键字key
,则设置start = mid + 1
; - 再次计算
mid = (start + end) // 2
; - 重复3和4直到找到关键字或者
start
和end
相遇。
key =
lst.sort()
start = 0
end = len(lst) - 1
flag = False
while start < end:
mid = (start + end) // 2
if lst[mid] > key:
end = mid - 1
elif lst[mid] < key:
start = mid + 1
else:
flag = True
break
if flag:
print(key)
else:
print('Not found.')
def binary_search(ls, key):
ls.sort()
start = 0
end = len(ls) - 1
mid = (start + end) // 2
while start < end:
if ls[mid] > key:
end = mid - 1
if ls[mid] < key:
start = mid + 1
if ls[mid] == key:
return True
mid = (start + end) // 2
return False
利用二分法查找求平方根
要利用二分法的算法求平方根,需要注意的是一个正数的平方根是一定存在的,假设求一个有两位小数的平方根,大致的步骤如下 :
- 设置起始和末尾节点
start
、end
,如果这个数key
大于1
, 则start = 1
,end = key
; 如果key
小于1,则start = key
,end = 1
; - 计算
mid = (start + end) / 2
- 如果
mid * mid
的结果与key
的差值的绝对值小于0.0001
,则确定mid
为key
的平方根; - 如果
mid * mid
大于key
, 则设置end = mid
,反之设置start = mid
; - 再次计算
mid = (start + end) / 2
; - 重复4和5直到找到平方根为止。
key = float(input("请输出一个有两位小数的浮点数:"))
if key > 1:
start = 1
end = key
else:
start = key
end = 1
mid = (start + end) / 2
while abs(mid * mid - key) > 0.0001:
if mid * mid > key:
end = mid
if mid * mid < key:
start = mid
mid = (start + end) / 2
print(round(mid, 2))