数据结构与算法：二分查找

zsirfs 发布于2019-08-23 15:33 / 1896人阅读

摘要：为检查长度为的列表，二分查找需要执行次操作。最后需要指出的一点是高水平的读者可研究一下二叉树关于二叉树，戳这里数据结构与算法二叉树算法常见练习在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。

常见数据结构

简单数据结构（必须理解和掌握）

有序数据结构：栈、队列、链表。有序数据结构省空间（储存空间小）

无序数据结构：集合、字典、散列表，无序数据结构省时间（读取时间快）

复杂数据结构

树、堆

图

本系列主要内容

数组和列表：最常用的数据结构

与链表相比，数组具有更好的缓存位置。

栈和队列：与列表类似但是更复杂数据结构

链表：如何通过它们克服数组的不足，

链表允许在迭代期间有效地从序列中的任何位置插入或删除元素。

链表的一个缺点是访问时间是线性的(而且难以管道化)。（更快的访问，如随机访问，是不可行的）

字典：将数据以键-值对的的形式储存

散列(表)：适用于快速查找和检索

集合：适用于存储只出现一次的元素

二叉树：以层级的形式存储数据

图和图算法：网络建模的理想选择

算法：包括排序、搜索、图形算法

高级算法：动态规划、贪心算法、BF、分治、回溯等算法范式

加密算法：

有序数据结构 数组列表栈队列链表 无序列数据结构 集合字典 散列(表) 简单算法 => 二分查找

二分查找是搜索算法中的一种，用来搜索有序数组

二分查找：是一种简单算法，其输入是一个有序的元素列表（必须有序的原因稍后解释）。如果要
查找的元素包含在列表中，二分查找返回其位置；否则返回null。

Javascript ES6实现 非递归的

/** 
 * 函数binarySearch接受一个有序数组和一个元素。 如果指定的元素包含在数组中， 这个
 函数将返回其位置。 你将跟踪要在其中查找的数组部分—— 开始时为整个数组。
*/
const binarySearch = (list, item) => {
  // 数组要查找的范围
  // low、high用于跟踪要在其中查找的列表部分
  let low = 0  
  let high = list.length - 1

  while(low <= high) { // 只要范围没有缩小到只包含一个元素
    const mid = Math.floor((low + high) / 2)
    const guess = list[mid] // 找到中间的元素

    if(guess === item) { // 找到元素
      return mid
    }
    if(guess > item) { // 猜测的数大了
      high = mid - 1
    } else {　// 猜测的数小了
      low = mid + 1
    }
  }

  return null
}

const myList = [1, 3, 5, 7, 9]

console.log(binarySearch(myList, 3))
console.log(binarySearch(myList, -1))

递归的

 
const binarySearch = (list, item, low, hight) => {
  let arrLength = list.length
  while (low <= high) {
    let mid = Math.floor((low + high) / 2)
    let guess = list[mid]

    if( guess === item ) {
      return mid
    } else if (guess > item) {
      high = mid - 1
      list = list.slice(0, mid)
      return binarySearch(list, item, low, high)
    } else {
      low = mid + 1
      list = list.slice(low, arrLength)
      return binarySearch(list, item, low, high)
    }
  }
  return null 
}

const createArr = (n) => Array.from({length: n}, (v, k) => k + 1)

const myList = createArr(100)
let low = 0
let high = myList.length - 1

console.log(binarySearch(myList, 3, low, high))
console.log(binarySearch(myList, -1, low, high))

找一个平衡二叉树最后一个节点

Python实现 运行时间(时间复杂度)

二分查找的运行时间为对数时间（或log时间）。
如果列表包含100个元素，最多要猜7次；如果列表包含40亿个数字，最多
需猜32次。

即：　２的７次方 = 100

简单查找时间是　ｙ= ax 的线性方方程
所以很容易得出结论

随着元素数量的增加（ｘ增加），二分查找需要的时间（ｙ）并不多， 而简单查找需要的时间（ｙ）却很多。
因此，随着列表的增长，二分查找的速度比简单查找快得多。

为检查长度为n的列表，二分查找需要执行log n次操作。使用大O表示法，
这个运行时间怎么表示呢？O(log n)。一般而言，简单算法的大O表示法像下面这样

大O符号

大O符号中指定的算法的增长顺序

以下是一些最常用的 大O标记法 列表以及它们与不同大小输入数据的性能比较。

O(log n)，也叫对数时间，这样的算法包括二分查找

O(n)，也叫线性时间，这样的算法包括简单查找。

O(n * log n)，这样的算法包括快速排序——一种速度较快的排序算法。

,这样的算法包括选择排序——一种速度较慢的排序算法

O(n!)，这样的算法包括接下来将介绍的旅行商问题的解决方案——一种非常慢的算法

小结

算法的速度指的并非时间，而是操作数的增速。

谈论算法的速度时，我们说的是随着输入的增加，其运行时间将以什么样的速度增加。

算法的运行时间用大O表示法表示。

O(log n)比O(n)快，当需要搜索的元素越多时，前者比后者快得越多

快速排序

快排和二分查找都基于一种叫做「分治」的算法思想，通过对数据进行分类处理，不断降低数量级，实现O(logN)（对数级别，比O(n) 这种线性复杂度更低的一种，快排核心是二分法的O(logN) ，实际复杂度为O(N*logN) ）的复杂度。

快排大概的流程是：

随机选择数组中的一个数 A，以这个数为基准

其他数字跟这个数进行比较，比这个数小的放在其左边，大的放到其右边

经过一次循环之后，A 左边为小于 A 的，右边为大于 A 的

这时候将左边和右边的数再递归上面的过程

旅行商问题--复杂度O(n!)的算法

简单的讲如果旅行者要去５个城市，先后顺序确定有５＊４＊３＊２＊１　＝　１２０种排序。（这种排序想想高中时候学到过的排序知识）

推而广之,涉及n个城市时,需要执行n!(n的阶乘)次操作才能计算出结果。因此运行时间
为O(n!),即阶乘时间。除非涉及的城市数很少,否则需要执行非常多的操作。如果涉及的城市
数超过100,根本就不能在合理的时间内计算出结果——等你计算出结果,太阳都没了。

这种算法很糟糕!,可别无选择。这是计算机科学领域待解的问题之一。对于这个问题,目前还没有找到更快的算法,有些很聪明的人认为这个问题根本就没有更巧妙的算法。
面对这个问题,我们能做的只是去找出近似答案。

最后需要指出的一点是,高水平的读者可研究一下二叉树

关于二叉树，戳这里: 数据结构与算法:二叉树算法

常见练习

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

参考

算法图解
JavaScript 算法与数据结构
https://github.com/egonSchiel...
【算法】时间复杂度
【算法】空间复杂度
InterviewMap 时间复杂度
https://github.com/trekhleb/j...
每周一练之数据结构与算法（Stack）
All Algorithms implemented in Python

GPU云服务器云服务器二分查找二分查找代码二分法查找二分查找c语言实例

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/102227.html

数据结构与算法——二分查找

摘要：所以，二分查找较适用于一次排序，多次查找的数据。面对大量的数据，二分查找方能体现其优势。 1. 二分查找的思想二分查找是一种使用十分普遍的查找算法，其基本的思路也非常的简单，在一个有序的数据集合中，我们想要查找某个数据，直接取最中间的那个数据，将它和要找的数据进行比较，如果较大，则在更大的那个数值区间继续取中间值查找，反之亦然。例如我们要在一个有序的集合里[1，3，5，6，7，8，...

boredream 2019-08-16 16:02 评论0 收藏0
数据结构与算法：二分查找

摘要：为检查长度为的列表，二分查找需要执行次操作。最后需要指出的一点是高水平的读者可研究一下二叉树关于二叉树，戳这里数据结构与算法二叉树算法常见练习在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。常见数据结构简单数据结构（必须理解和掌握）有序数据结构：栈、队列、链表。有序数据结构省空间（储存空间小）无序数据结构：集合、字典、散列表，无序...

you_De 2019-08-16 15:26 评论0 收藏0
数据结构与算法：二分查找

摘要：为检查长度为的列表，二分查找需要执行次操作。最后需要指出的一点是高水平的读者可研究一下二叉树关于二叉树，戳这里数据结构与算法二叉树算法常见练习在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。常见数据结构简单数据结构（必须理解和掌握）有序数据结构：栈、队列、链表。有序数据结构省空间（储存空间小）无序数据结构：集合、字典、散列表，无序...

gotham 2019-07-31 10:07 评论0 收藏0
【二分查找】| 模拟 20 万数据快速查询 IP 归属地

摘要：通过两个二分查找的条件继续进行问题的分析，那么问题又来了，二分查找是快速的查找一个数据是否存在一组数据中，而且效率极高，亿查找一个数据只需次查找。二分查找的三点重点循环退出条件注意是而不是。 showImg(https://segmentfault.com/img/remote/1460000018761246);这篇文章主要深入数据结构与算法在解决实际问题怎么运用和分析的，对于 IP...

The question 2019-08-23 16:44 评论0 收藏0
数据结构与算法——二分查找练习

摘要：查找最后一个等于给定值的元素这种变形的二分查找和上面的这种情况很类似，还是利用上面的那个数组，我们要查找最后一个等于的元素。 1. 概述前面说到了二分查找问题，看起来非常的简单，的确，前面的两种实现都不难，代码也很容易写，因为那只是最基础的二分查找问题了。今天来看看几种稍微复杂的二分查找问题：查找第一个等于给定值的元素查找最后一个等于给定值的元素查找第一个大于等于给定值的元素...

JasinYip 2019-08-16 16:05 评论0 收藏0