二分查找是搜索算法中的一种，用来搜索有序数组
二分查找： 是一种简单算法，其输入是一个有序的元素列表（必须有序的原因稍后解释）。如果要
查找的元素包含在列表中，二分查找返回其位置；否则返回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 = 0let high = myList.length - 1console.log(binarySearch(myList, 3, low, high))console.log(binarySearch(myList, -1, low, high)) Python实现
运行时间(时间复杂度)
二分查找的运行时间为对数时间（或log时间）。
如果列表包含100个元素，最多要猜7次；如果列表包含40亿个数字，最多需猜32次。
即： ２的７次方 = 100 
随着元素数量的增加（ｘ增加），二分查找需要的时间（ｙ）并不多， 而简单查找需要的时间（ｙ）却很多。 因此，随着列表的增长，二分查找的速度比简单查找快得多。
为检查长度为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(n!)的算法
简单的讲如果旅行者要去５个城市，先后顺序确定有５＊４＊３＊２＊１ ＝ １２０种排序。（这种排序想想高中时候学到过的排序知识）
推而广之,涉及n个城市时,需要执行n!(n的阶乘)次操作才能计算出结果。因此运行时间 为O(n!),即阶乘时间。除非涉及的城市数很少,否则需要执行非常多的操作。如果涉及的城市 数超过100,根本就不能在合理的时间内计算出结果——等你计算出结果,太阳都没了。
这种算法很糟糕!,可别无选择。这是计算机科学领域待解的问题之一。对于这个问题,目前还没有找到更快的算法,有些很聪明的人认为这个问题根本就没有更巧妙的算法。
面对这个问题,我们能做的只是去找出近似答案。最后需要指出的一点是,高水平的读者可研究一下二叉树
关于二叉树，戳这里: