数据结构与算法Day5 搜索算法

1187-吴同学

发表文章数:41

首页 » 数据结构 » 正文

搜索

搜索是在一个项目集合中找到一个特定项目的算法过程。搜索的几种常见方法:顺序查找、二分法查找、二叉树查找、哈希查找。

二分法查找

二分查找又称折半查找。

优点 缺点 适用对象
比较次数少,查找速度快,平均性能好 要求待查表为有序表,且插入删除困难 不经常变动而查找频繁的有序列表

具体操作

  1. 假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较。
  2. 若两者相等,则查找成功;否则利用中间位置将表分成前、后两个子表:若中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。
  3. 重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。
    数据结构与算法Day5 搜索算法

算法实现

递归方法

def binary_search(alist, item):
    """二分法查找"""
    if not alist:
        return False
    n=len(alist)
    mid=n//2
    if alist[mid]==item:
        return True
    elif alist[mid]>item:
        return binary_search(alist[:mid],item)
    else:
        return binary_search(alist[mid+1:],item)

非递归方法

def binary_search(alist, item):
    """二分法查找,非递归"""
    n=len(alist)
    first=0
    last=n-1 #最后的位置要长度减一,勿忘
    while first<=last:
        mid=(first+last)//2
        if alist[mid]==item:
            return True
        elif alist[mid]>item:
            last=mid-1
        else:
            first=mid+1
    return False

时间复杂度

最优时间复杂度:

O

(

1

)

O(1)

O(1)
最坏时间复杂度:

O

(

log

n

)

O(/log n)

O(logn)

未经允许不得转载:作者:1187-吴同学, 转载或复制请以 超链接形式 并注明出处 拜师资源博客
原文地址:《数据结构与算法Day5 搜索算法》 发布于2020-12-03

分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

Vieu3.3主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。

登录

忘记密码 ?

您也可以使用第三方帐号快捷登录

Q Q 登 录
微 博 登 录