专栏首页村雨算法图解 第1章 算法简介

算法图解 第1章 算法简介

二分查找

定义

一种算法,输入是一个有序的元素列表,如果查找的元素包含在列表中,则二分查找返回其位置,否则返回null

算法实现

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @version : 1.0
# @Time    : 2019-10-26 9:47
# @Author  : cunyu
# @Email   : cunyu1024@foxmail.com
# @Site    : https://cunyu1943.github.io
# @File    : binay_search.py
# @Software: PyCharm
# @Desc    : 二分查找

# 二分查找,其中list必须为有序列表
# list是要查找的数组,item是要查找的元素
def binary_search(list, item):
    # 起始位置初始化列表为第一个元素
    low = 0
    # 终止位置为列表最后一个元素
    high = len(list) - 1
    # 循环到范围只包含一个元素
    while low <= high:
        mid = (low + high) // 2
        guess = list[mid]
        # 若找到需要查找的元素
        if guess == item:
            return mid
        # 若猜的数字大于查找的元素
        elif guess > item:
            high = mid - 1
        # 若猜的数字小于查找的元素
        else:
            low = mid + 1;
    # 若未找到指定元素
    return None


if __name__ == '__main__':
    my_list = [3, 4, 8, 11, 13, 20]
    item = int(input('输入你要查找的元素\n'))
    print('元素 ' + str(item) + ' 的索引位置(从0开始):')
    print(binary_search(my_list, item))

练习

  1. 一个含有128个元素的有序列表,使用二分查找查找某元素,最多需要几步?

,所以最多需要7步就可以找到指定元素;

  1. 1中列表长度翻倍后,最多需几步?

翻倍后,,所以最多需要8步;

运行时间

  • 线性时间(linear time):所需时间与查询列表长度成线性关系,则成为线性时间;
  • 对数时间(log time)

简单查找

二分查找

100个元素最多需100次

100个元素最多需7次

10000个元素最多需10000次

10000个元素最多需14次

线性时间

对数时间

大表示法

一种特殊表示法,指出算法速度;

常见大运行时间

  • :对数时间,如二分查找;
  • :线性时间,如简单查找;
  • :如快速排序;
  • :如选择排序;
  • !:如旅行商问题;

总结

  • 算法速度并非时间,而是操作数的增速;
  • 算法运行时间用大表示法表示;
  • 快于,当搜索元素较多时,前者比后者快得多;

本文分享自微信公众号 - 村雨1943(cunyu1943),作者:村雨1943

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-10-29

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Python中关于面向对象的相关知识

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    村雨
  • Github加载及下载问题

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    村雨
  • NLTK相关知识介绍

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    村雨
  • 八爪鱼采集器︱加载更多、再显示20条图文教程(Xpatth、Ajax)

    由于代码布置采集器比较麻烦,又很早知道八爪鱼采集器的强大,所以把一些常规的采集内容贴成图文教程,供以后使用。

    素质
  • Super快报第22期:最不安全的互联网公司

    1、360是最不安全的公司? 《每日经济新闻》做了几个月调查,得出结论:360的成功不在于“破坏性创新”,而在于“创新型破坏”:通过破坏,打破既有规则,从...

    罗超频道
  • ThreadLocal详解

      这个玩意有什么用处,或者说为什么要有这么一个东东?先解释一下,在并发编程的时候,成员变量如果不做任何处理其实是线程不安全的,各个线程都在操作同一个变量,显然...

    lyb-geek
  • 为什么说每个人都应该有台Mac电脑?

    昨天跟一个朋友聊天,最近想买个电脑,让我给推荐款,我说国产的性价比都还可以作为开发用最好是cpu i5以上,内存至少也得8G了,网上一搜基本上一堆,推荐了半天最...

    程序员互动联盟
  • 第101天:CSS3中transform-style和perspective

    1、transform-style属性是3D空间一个重要属性,指定嵌套元素如何在3D空间中呈现。

    半指温柔乐
  • 机器学习API Top 10:AT&T Speech、IBM Watson和Google Prediction

    【编者按】随着机器学习算法的流行,Amazon、Google,、IBM和Microsoft等公司在机器学习云服务市场接连出手,并提供许多的API来吸引用户。本文...

    CSDN技术头条
  • 机器学习API Top 10:AT&amp;T Speech、IBM Watson和Google Prediction

    用户1737318

扫码关注云+社区

领取腾讯云代金券