【数据结构与算法】7_python版 _搜索

文章目录一、搜索1.1 二分法查找1.2 二分法查找的分析1.3 二分法查找的代码实现1.4 二分法查找的时间复杂度一、搜索搜索是在一个项目集合中找到一个特定项目的算法过程。搜索通常的答案是真的或假的因为该项目是否存在。 搜索的几种常见方法顺序查找、二分法查找、二叉树查找、哈希查找1.1 二分法查找二分查找又称折半查找优点是比较次数少查找速度快平均性能好其缺点是要求待查表为有序表且插入删除困难。因此折半查找方法适用于不经常变动而查找频繁的有序列表。首先假设表中元素是按升序排列将表中间位置记录的关键字与查找关键字比较如果两者相等则查找成功否则利用中间位置记录将表分成前、后两个子表如果中间位置记录的关键字大于查找关键字则进一步查找前一子表否则进一步查找后一子表。重复以上过程直到找到满足条件的记录使查找成功或直到子表不存在为止使查找成功或直到子表不存在为止此时查找不成功。1.2 二分法查找的分析二分查找的操作对象首先是排序过之后的紧接着才可以进行二分查找。1、操作对象排序过之后2、元素相邻排放操作对象支持下标索引。列表支持下标索引也就是顺序表链表不支持因此二分查找只能作用于顺序表而且是有序的顺序表1.3 二分法查找的代码实现# 二分查找# 操作对象必须有序即已经按从小到大排好顺序# 最好描述和好写的是递归实现defbinary_search(alist,item):二分查找递归的方式产生新的列表nlen(alist)ifn0:midn//2ifalist[mid]item:returnTrueelifitemalist[mid]:returnbinary_search(alist[:mid],item)else:returnbinary_search(alist[mid1:],item)returnFalsedefbinary_search_2(alist,item):二分查找非递归的方式:不产生新的列表只是在原有的列表上进行操作nlen(alist)first,last0,n-1whilefirstlast:mid(firstlast)//2ifalist[mid]item:returnTrueelifitemalist[mid]:lastmid-1else:firstmid1returnFalseif__name____main__:li[16,20,26,31,44,54,55,77,93]resbinary_search_2(li,16)print(res)# Trueprint(binary_search_2(li,100))# False1.4 二分法查找的时间复杂度最优时间复杂度O(1)最坏时间复杂度O(logn)