数据结构与算法：二分查找
source link: https://studygolang.com/articles/18557?amp%3Butm_medium=referral
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
二分查找是搜索算法中的一种，用来搜索 有序数组
二分查找：是一种简单算法，其输入是一个有序的元素列表（必须有序的原因稍后解释）。如果要
查找的元素包含在列表中，二分查找返回其位置；否则返回 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次。
即：２的７次方 = 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)快，当需要搜索的元素越多时，前者比后者快得越多
参考
Recommend
-
47
二分法查找，也称为折半法，是一种在有序数组中查找特定元素的搜索算法。所以在采用二分法查找时，数据需是有序不重复的，如果是无序的也可通过选择排序、冒泡排序等数组排序方法进行排序之后，就可以使用二分法查找。 基本...
-
10
如何运用二分查找算法 👆让天下没有难刷的算法！若 GitBook 访问太慢，可尝试
-
17
”二分查找“算法的时间复杂度 算法的时间复杂度无非就是for、while等包含起来的基本运算单元的循环次数 1、二分查找二分查找（binary search...
-
7
你是那10%可以实现二分查找算法的程序员吗？ 浏览:5918次 出处信息 原文链接：
-
10
数据结构之二分查找
-
12
Mr.Feng BlogNLP、深度学习、机器学习、Python、Go经典的二分查找算法体会下经典的二分查找算法。二分操作算法只能由于有序数组，时间复杂度是O(lgN)。在链表情况...
-
11
这里总结了一些前端常见的算法。1、排序问题1.1冒泡排序该算法就是依次比较大小，小的的大的进行位置上的交换。var ex=[8,95,34,21,53,12];
-
8
一文搞懂二分查找算法！-51CTO.COM 一文搞懂二分查找算法！ 作者：月伴飞鱼 2022-03-28 10:03:58 从定义可知，运用二分搜索的前提是数组必须是排好序的，另外，输入并不一定是数组，也有可能是给...
-
4
LC T668笔记 & 有关二分查找、第K小数、BFPRT算法 LC T668笔记 【...
-
5
二分查找 二分查找 二分查找（Binary Search）也叫作折半查找，前提是查找的顺序结构是有序的，我们一般在数组上进行二分查找。 二分查找就好像猜数字大小游戏一样。假设要数字目标值...
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK