找回密码
 立即注册

扫一扫,访问微社区

QQ登录

只需一步,快速开始

查看: 3838|回复: 4

其实 两分搜索 和 线性搜索 差距没那么大

11

主题

35

帖子

35

积分

贫民

积分
35
zy1 发表于 2014-10-1 11:46:58 | 显示全部楼层 |阅读模式
测了一下两分搜索 和 线性搜索的运行时间,用的都是由小到大排序好的数组,搜最大的数
线性搜索
数组大小运行时间(s)
100000.01
1000000.02
10000000.07
100000000.5
两分搜索
数组大小运行时间(s)
100000.01
1000000.015
10000000.05
100000000.3


代码如下:

def sequentialSearch(a, item):

        for i in a:

                if i == item: return True

            return False



def binarySearch(a, item):

    l = 0

    r = len(a)-1

    m = m_v = 0

    while l <= r:

        m = (l+r)//2

        m_v = a[m_v]

        if m_v == item: return True

        else:

            if item < m_v: r = m-1

            else: l = m+1

        return False

回复

使用道具 举报

50

主题

1057

帖子

1108

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
1108

活跃会员热心会员最佳导师默默耕耘突出贡献优秀版主荣誉管理论坛元老

blueelwang 发表于 2014-10-22 17:30:30 | 显示全部楼层
不错,实践最重要,不要盲从,网上的很多资料未必是对的
回复 支持 反对

使用道具 举报

11

主题

35

帖子

35

积分

贫民

积分
35
zy1  楼主| 发表于 2014-11-3 02:33:20 | 显示全部楼层
blueelwang 发表于 2014-10-22 17:30
不错,实践最重要,不要盲从,网上的很多资料未必是对的

谢管理员捧场,有好东西我会继续post上来
回复 支持 反对

使用道具 举报

50

主题

1057

帖子

1108

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
1108

活跃会员热心会员最佳导师默默耕耘突出贡献优秀版主荣誉管理论坛元老

blueelwang 发表于 2014-11-14 17:42:58 | 显示全部楼层
西红丝炒番茄 发表于 2014-11-14 09:28
不错,实践最重要,不要盲从,网上的很多资料未必是对的,很多都是水贴

是这个意思
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表