<span role="heading" aria-level="2">js算法初窥03（搜索及去重算法）

大家好，又见面了，我是你们的朋友全栈君。

　　前面我们了解了一些常用的排序算法，那么这篇文章我们来看看搜索算法的一些简单实现，我们先来介绍一个我们在实际工作中一定用到过的搜索算法——顺序搜索。

1、顺序搜索

　　其实顺序搜索十分简单，我们还是以第一篇文章写好的架子作为基础，在其中加入顺序搜索的方法：

//顺序搜索
this.sequentialSearch = function(item) {
    for(var i = 0; i < array.length; i++) {
        if(item === array[i]) {
            return i;
        };
    };
    return -1;
};

　　我想这个代码没什么好说的。你一定能理解的十分透彻。那么下面我们来看看二分搜索。

2、二分搜索

　　我们先来做一个简单的游戏。想象一个场景，我们在聚会，大约有7、8个人，这个时候有人提议我们来做个游戏吧。我来想一个1到100的数字，你们来猜数字是什么，我会依照我想的数字告诉你们猜测的数字是比我脑海中的数字大了还是小了。这就是二分搜索。

　　与顺序搜索不同的是，二分搜索需要在搜索之前对要搜索的数组排序。我们来看下代码：

//二分搜索
this.binarySearch = function(item) {
    //先对数组进行快速排序
    this.quickSort();
    //low和high是边界指针，也就是item是高了还是低了的表示，mid是我们数组的中间索引变量，element则是对应的mid的元素
    var low = 0,high = array.length - 1,mid,element;
    //如果low小于等于high说明边界范围是合理的。
    while(low <= high) {
        //为mid和element变量赋值。
        mid = Math.floor((low + high) / 2);
        element = array[mid];
        // 如果中间值比我们要找的元素小，说明item在中间值的右侧，要注意我们的数组时排序过后的数组了。
        // 所以我们直接让等于0的low的值设置为mid+1,因为item>element，所以item必然在mid+1开始到high的区间范围内。
        // 下同。
        if(element < item) {
            low = mid + 1;
        } else if(element > item) {
            high = mid - 1;
        } else {
            return mid;
        };
    };
    return -1;
};

　　其实二分搜索也并不难，看代码和注释就一定可以看懂的。感觉这篇内容实在是不太多，所以我决定再加入一些其他的内容吧。

3、去重

　　想必大家在面试中被问到过最多的问题就是排序和去重了吧。其实这个东西真的算是老生常谈了，但是却又有它存在的必要，其实说到底，去重更重要的是思想，而不是实现，就跟前面我们学过的那些数据结构和算法一样。

　　下面我们就介绍一下去重的一些实现方法吧。

　　1）set方法

　　　　set是ES6新增的一种数据结构——集合，我在前面的有关集合的章节中也介绍过这种数据结构，集合是一种不允许重复的数据存在的数据结构，我们刚好可以利用这种特性来为数组去重。如果你还不了解set数据结构，可以去这里或者这里查看。

this.uniqueSetWay = function () {
    //array.form方法从类似数组或可迭代对象中创建一个新的数组实例
    var set = new Set(array);
    return Array.from(set);
};

//测试方法
var repeatArray = new ArrayList();
repeatArray.insert(1);
repeatArray.insert(1);
repeatArray.insert(3);
repeatArray.insert(3);
repeatArray.insert(5);
repeatArray.insert(7);
repeatArray.insert(7);
repeatArray.insert(9);
repeatArray.insert(9);
repeatArray.insert(8);
console.log(repeatArray.uniqueSetWay())

　　　　要注意的是，我们这里仍旧使用了第一章所构建的数组类。

　　2）双循环

//双循环
this.uniqueDoubleCycle = function () {
     var newArr = [];
    var len = array.length;
    var isRepeat;
  
    for(var i=0; i<len; i++) {  //第一次循环
        isRepeat = false;
        for(var j=i+1; j<len; j++) {  //第二次循环
            if(array[i] === array[j]){
                isRepeat = true;
                break;
            }
        }
        if(!isRepeat){
            newArr.push(array[i]);
        }
    }
    return newArr;
};

　　　　这种方法使用了双重循环设置一个标记位，确定我们加入新数组的元素是否是重复的，代码很好理解，但是这是效率最低的实现方式。

　　3）排序辅助去重

//利用排序算法来辅助判断
this.sortUnique = function () {
    var newArr = [];                  
     this.quickSort();
     //将原数组中的第一项放入新数组
      var newArr = [array[0]];
      // 我们来循环比较
      for(var i = 1; i < array.length; i++){
          //如果新数组中的最后一项与array[i]不想等，那么我们就把它加入新数组。
        if(array[i] !== newArr[newArr.length - 1]){
             newArr.push(array[i]);
            }
      }    
      return newArr;
};