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

对于前端初学者而言，这样的一个功能你做出来了那就很好，慢慢的，我们的工作年限越来越长，如果我们还继续那样做，这样，迟早会淘汰。这个时候，就需要对你的项目进行优化。之前讲到过对于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)