python从入门到马上不行了
一.查找表1.查找表2.静态查找表和动态查找表3.关键字
二.顺序查找算法1.算法描述2.代码实现
三.折半查找算法1.算法描述2.折半查找的性能分析3.代码实现
一.查找表
1.查找表
查找表是由同一类型的数据元素构成的集合。例如电话号码簿和字典都可以看作是一张查找表。 一般对于查找表有以下几种操作:
在查找表中查找某个具体的数据元素;在查找表中插入数据元素;从查找表中删除数据元素;
2.静态查找表和动态查找表
在查找表中只做查找操作,而不改动表中数据元素,称此类查找表为静态查找表;在查找表中做查找操作的同时进行插入数据或者删除数据的操作,称此类表为动态查找表。
3.关键字
关键字又细分为主关键字和次关键字。
若某个关键字可以唯一地识别一个数据元素时,称这个关键字为主关键字,例如学生的学号就具唯一性;像学生姓名、年龄这类的关键字,由于不具有唯一性,称为次关键字。
二.顺序查找算法
1.算法描述
从表中的最后一个数据元素开始,逐个同记录的关键字做比较,
如果匹配成功,则查找成功;如果直到表中第一个关键字查找完也没有成功匹配,则查找失败。
2.代码实现
def sequence_search(array
, key
):
"""
顺序查找算法
"""
for i
in range(len(array
)):
if array
[i
] == key
:
return i
return False
array_0
= [23, 43, 12, 54, 65, 48]
print(sequence_search
(array_0
, 12))
三.折半查找算法
1.算法描述
2.折半查找的性能分析
折半查找的运行过程可以用二叉树来描述,这棵树通常称为“判定树”。
3.代码实现
def halffind(nums
, key
, low
, high
):
"""
二分查找递归实现
"""
mid
= (low
+ high
) // 2
if key
== nums
[mid
]:
return mid
if low
> high
:
return False
if key
> nums
[mid
]:
return halffind
(nums
, key
, mid
+ 1, high
)
else:
return halffind
(nums
, key
, low
, mid
- 1)
if __name__
== "__main__":
nums
= [-789, -96, -53, 23, 52, 56, 520]
key
= int(input("请输入要搜索的关键字:"))
print(halffind
(nums
, key
, 0, len(nums
)))