算法:二分查找

栏目: 编程工具 · 发布时间: 5年前

内容简介:级别: ★☆☆☆☆标签:「算法」「二分查找」「大O表示法」作者:MrLiuQ

级别: ★☆☆☆☆

标签:「算法」「二分查找」「大O表示法」

作者:MrLiuQ

审校:QiShare团队

前言:最近小编在看《算法图解》,将会总结一系列算法相关的文章。

关于算法的系列文章,小编将准备分“三步”来编写:

Python

本篇将介绍 二分查找大O表示法 ,并为后续的算法文章打下算法基础。

一、算法简介

算法,简单来说,就是一组完成任务的指令。任何代码片段都可视为算法。

算法的用途主要有两个方面:

  • 一:提高代码的运行速度,优化业务逻辑。 => 已达到提高代码质量的目的。
  • 二:解决实际应用问题。 => 已达到完成业务需求的目的。
算法的用途 目的
提高代码运行速度,优化业务逻辑 提高代码质量
解决实际应用问题 完成业务需求

二、二分查找

问题:假设有一个有序数组(前提: 有序 数组),我们要查询一个数在这个数组中的位置(index),我们应该如何查找?

先介绍一个 简单暴力 的查找方式:直接遍历一遍这个数组,找到对应的数后再返回index。这个方法我们称之为——简单查找。

2.1 简单查找:

直接遍历数组查找元素。很简单很暴力。

算法:二分查找

基于 Python 的算法:

def easy_search(list, item):
    for index in range(len(list)):
        if list[index] == item:
            return index
    return None
复制代码

测评:

简单查找在运气好时(即遍历的第一个元素即为该数),只需要查找一次。 但是当如果所找元素在数组末尾时,就要一直遍历到最后一个元素才能找到那个数。n个元素的数组要找n次。

这显然效率会不高,这时候我们可以使用:二分查找法。

2.2 二分查找:

二分查找,顾名思义,每次查找将数组分成两部分,从中间开始找。

  • 如果发现数比中间数大,即数在 中间数最大数 之间,就修改 low 的值。再对比中间值。
  • 如果发现数比中间数小,即数在 最小数中间数 之间,就修改 high 的值。再对比中间值。
算法:二分查找
def binary_search(list, item):
    low = 0
    high = len(list) - 1

    while low <= high:
        mid = (low + high) / 2
        if list[mid] == item:
            return mid
        if list[mid] > item:
            high = mid - 1
        else:
            low = mid + 1
    return None
复制代码

这样,每次循环就能舍去一半的元素,大大提高了查找的效率。这就是二分查找法。

三、大O表示法

时间复杂度由 大O表示法 描述。

  • 时间复杂度描述的是算法的运行效率;
  • 时间复杂度指的并非具体时间,而是操作数的增速。

运用简单查找算法,在n个元素的数组中查找一个数,情况最遭时,需要n步,所以简单查找的时间复杂度是 O(n)

运用二分查找算法,在n个元素的数组中查找一个数,情况最遭时,需要(log n)步,所以二分查找的时间复杂度是 O(log n)

工程源码: QiAlgorithms

小编微信:可加并拉入《QiShare技术交流群》。

算法:二分查找

关注我们的途径有:

QiShare(简书)

QiShare(掘金)

QiShare(知乎)

QiShare(GitHub)

QiShare(CocoaChina)

QiShare(StackOverflow)

QiShare(微信公众号)


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

網絡社會之崛起

網絡社會之崛起

曼威·柯司特 / 夏鑄九、王志弘 等 / 唐山 / 2000-11 / NT$550

本書解釋了今日重塑世界的兩股強大但相互衝突的潮流:全球化與認同。資訊科技的革命以及資本主義的再結構已經引動了網絡社會,並帶來了策略,除經濟行為的全球化、工作的彈性化與不穩定,以及真實的虛擬文化。但是,伴隨著資本主義的轉化與國家主義的消亡而來的,是集體認同的表達以火力十足的方式竄起。它們挑戰了全球化中的文化單一性以及對於生活、環境的控制。曼威.柯司特在本書中描繪了社會運動的根源、目標以及效果,包括了......一起来看看 《網絡社會之崛起》 这本书的介绍吧!

JS 压缩/解压工具
JS 压缩/解压工具

在线压缩/解压 JS 代码

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换