前端之算法（五）顺序和二分搜索

Augus

关注

发布于: 4 小时前

大家好，前几章我们讲了冒泡，选择，插入，归并和快速排序，了解了一些比较熟知的排序算法，今天呢我们要聊的就是顺序和二分搜索，是两种搜索算法，理解后对我们的实际工作还是很有用处的，接下来让我们来看看这两种搜索算法吧！

顺序搜索

这种算法非常低效，但是非常适合入门，

顺序搜索的思路

遍历数组。
找到跟目标相等的元素，就返回它的下标。
遍历结束后，如果没有搜索到目标值，就返回 -1。

实现

Array.prototype.sequentialSearch = function (item) {    for (let i = 0; i < this.length; i++) {        if (this[i] === item) {            return i        }    }    return -1}
const res = [1, 2, 3, 4, 5]console.log(res.sequentialSearch(3));console.log(res.sequentialSearch(6));// 2 -1

复制代码

顺序搜索的时间复杂度

遍历数组是一个循环操作。
时间复杂度：O(n)。

二分搜索

二分搜索又称折半搜索，是一种在 有序数组 中查找某个特定元素的算法，它比顺序搜索的效率要高的多，因为每次搜索都会减半，而不用像顺序搜索一样把每个元素都遍历一遍。

二分搜索的思路

从数组的中间元素开始，如果中间元素正好是目标值，则搜索结束。
如果目标值大于或者小于中间的元素，则在大于或小于中间元素的那一半数组中搜索。
如果搜索到最后还没找到目标值，就返回 -1。

实现

Array.prototype.binarySearch = function (item) {    let low = 0    let high = this.length - 1    while (low <= high) {        const mid = Math.floor((low + high) / 2)        const element = this[mid]        if (element < item) {            low = mid + 1        } else if(element > item) {            high = mid - 1        } else {            return mid        }    }    return -1}
const res = [1, 2, 3, 4, 5]console.log(res.binarySearch(3));console.log(res.binarySearch(6));// 2 -1

复制代码

二分搜索的时间复杂度

每一次比较都使搜索范围缩小一半。
时间复杂度：O(logN)。

End~~

发布于: 4 小时前阅读数: 2

Augus

关注

爱瞎搞的软件开发工程师 2021.06.10 加入

某摸鱼集团

发布

暂无评论

创作场景

前端之算法（五）顺序和二分搜索

顺序搜索

顺序搜索的思路

实现

顺序搜索的时间复杂度

二分搜索

二分搜索的思路

实现

二分搜索的时间复杂度

Augus

评论