二分查找是搜索算法中的一种,用来搜索有序数组
二分查找: 是一种简单算法,其输入是一个有序的元素列表(必须有序的原因稍后解释)。如果要
查找的元素包含在列表中,二分查找返回其位置;否则返回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))
运行时间:
二分查找的运行时间为对数时间(或log时间)。
如果列表包含100个元素,最多要猜7次;如果列表包含40亿个数字,最多
需猜32次。
即: 2的7次方 = 100
简单查找时间是 y= ax 的线性方方程
所以很容易得出结论
随着元素数量的增加(x增加),二分查找需要的时间(y)并不多, 而简单查找需要的时间(y)却很多。
因此,随着列表的增长,二分查找的速度比简单查找快得多。
为检查长度为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)快,当需要搜索的元素越多时,前者比后者快得越多
参考
有疑问加站长微信联系(非本文作者)