Algorithms（一）

作者 johansen 日期 2017-01-24
技术小记
Algorithms（一）

又是一年又一年，后天赶车回家，今天有时间就以这篇文章结束猴年博客更新。回想今年过往，博客还是坚持了下来，习惯还在培养。希望鸡年有更高的提升。

搜索算法

说起数据结构我们就想到算法，生产工程中实际问题很多涉及到他，但对于前端来说很少有人去提到这一块，其实不然，算法是计算机的基础构建的核心，提高计算性能，减轻压力，算法起到至关重要的作用。
今天我们谈谈搜索相关的算法。

前端JS时长用到关于排重的操作，因此搜索去重是关键。怎么提高搜索的效率，需要一个好的算法进行优化。

算法介绍

  • 顺序搜索
    顺序搜索是最基本的搜索算法。它的机制是，将每一个数据结构中的元素和我们要找的元素做比较。顺序搜索是最低效的一种搜索算法。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    this.squentialSearch = function(item){
        for(var i=0;i<arr.length;i++)
        {  
            if(item == arr[i])
            {
            console.log('命中');
            }
        }
        return -1;
    }

  • 二分搜索法
    二分搜索算法的原理和猜数字游戏类似。
    这个算法要求被搜索的数据结构已排序。以下是该算法遵循的步骤。
    (1) 选择数组的中间值。
    (2) 如果选中值是待搜索值，那么算法执行完毕(值找到了)。
    (3) 如果待搜索值比选中值要小，则返回步骤1并在选中值左边的子数组中寻找。 (4) 如果待搜索值比选中值要大，则返回步骤1并在选种值右边的子数组中寻找。
    以下是其实现:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
        this.binarySearch = function(item){
          this.quickSort(); //首先对数组排序
          var low = 0,                
              high = array.length - 1, 
              mid, element;
          while (low <= high){ 
                mid = Math.floor((low + high) / 2); 
                element = array[mid];
                if (element < item) {
                    low = mid + 1;
                } else if (element > item) {
                    high = mid - 1;
                } else {
                    return mid;
                } 
            }
          return -1; 
    };

分析两个算法的时间复杂度如下

算法 数据结构 最差情况
顺序搜索 数组和链表 O(n)
二分搜索 排好序的数组或二分搜索树 O(log(n))
FEATURED TAGS
技术小记