二分搜索
原文链接:note.noxussj.top/?sou...
什么是二分搜索?
二分搜索是一种比较高效的搜索算法,但前提必须是有序数组。主要步骤如下:
- 从数组的中间元素开始,如果中间元素正好是目标值,则搜索结束
- 如果目标值大于或者小于中间元素,则在大于或者小于中间元素的那一半数组中继续二分搜索
基础案例
- 时间复杂度:O (logn)
- 空间复杂度:O (1)
Array.prototype.binarySearch = function (target) {
let low = 0
let high = this.length - 1
while (low <= high) {
const mid = Math.floor((low + high) / 2)
const element = this[mid]
if (element < target) {
low = mid + 1
} else if (element > target) {
high = mid - 1
} else {
return mid
}
}
return -1
}
const res = [1, 2, 3, 4, 5].binarySearch(1) // 0
因为每次比较都使搜索范围缩小一半,所以时间复杂度是 O (logn)。而空间复杂度是 O (1),因为没有使用线性增长的变量。
原文链接:note.noxussj.top/?sou...
本网站是一个以CSS、JavaScript、Vue、HTML为核心的前端开发技术网站。我们致力于为广大前端开发者提供专业、全面、实用的前端开发知识和技术支持。 在本网站中,您可以学习到最新的前端开发技术,了解前端开发的最新趋势和最佳实践。我们提供丰富的教程和案例,让您可以快速掌握前端开发的核心技术和流程。 本网站还提供一系列实用的工具和插件,帮助您更加高效地进行前端开发工作。我们提供的工具和插件都经过精心设计和优化,可以帮助您节省时间和精力,提升开发效率。 除此之外,本网站还拥有一个活跃的社区,您可以在社区中与其他前端开发者交流技术、分享经验、解决问题。我们相信,社区的力量可以帮助您更好地成长和进步。 在本网站中,您可以找到您需要的一切前端开发资源,让您成为一名更加优秀的前端开发者。欢迎您加入我们的大家庭,一起探索前端开发的无限可能!