阅读 6

前端基础算法--二分查找法

对于前端初学者而言,这样的一个功能你做出来了那就很好,慢慢的,我们的工作年限越来越长,如果我们还继续那样做,这样,迟早会淘汰。这个时候,就需要对你的项目进行优化。之前讲到过对于react项目的优化。这更多是针对于单页应用的优化,避免首页时间加载过长,打包文件加载过大,是针对于打包后文件来说的。这篇文章主要是针对于算法相关的代码进行优化,从而是程序的运行速度更快,已达到程序的优化。

算法更多的是针对于数据的增删改查,或许你认为前端涉及不到,如果这样想,那你就错了。前端可能用的不多,但不会涉及不到,同时,了解算法,那么对于以后的职业道路也会有所帮助。

二分查找法

二分查找在进行查找有序数组中某一项数据的时候非常有用,可以加快程序的运行速度,尤其是在具有大量数据的时候。

二分查找的原理是从数组的中间开始查找,如果被查找对象刚好就是中间这一项,那直接退出查找。如果被查找对象大于中间,那么所需要的对象是在中间-最后这一区间,所以有针对于这一区间再次进行二分。如此下去,找到所需要的即可。

/**
 * 二分查找
 * @param {Array} list  待查找的有序数组
 * @param {Number} item 待查找的数据
 */
function binarySearch(list, item){
    // 如果list不是数组返回list
    if (!Array.isArray(list)) return list
    // 定义查找的起始位置
    let low = 0;
    let high = list.length - 1;

    while (low <= high) {
        // 定义中间的位置
        let mid = Math.floor((low + high) / 2)
        let midValue = list[mid]

        if ( midValue == item ) return mid

        if (midValue < item){
            low = mid + 1
        }

        if (midValue > item){
            high = mid - 1
        }
    }

    return -1
}
复制代码

最后来看看一个具体的效果

const arr = []
for (let i = 0; i < 10000; i++) {
    arr.push(i)
}
const need = 6734
let res;

console.time("for")
for (let i = 0; i < arr.length; i++) {
  const ele = arr[i];
  if( ele === need ) {
    res = i
    break
  }
}
console.log(res);
console.timeEnd("for")

console.time("binarySearch")
res = binarySearch(arr, need)
console.log(res)
console.timeEnd("binarySearch")
复制代码

可以看到很明显二分查找比普通的循环遍历快了许多。

可视化链接

algorithm-visualizer.org/branch-and-…

时间复杂度 O(\log n)

关注下面的标签,发现更多相似文章
评论