前端开发--搜索算法

顺序搜索

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

arr = [5,4,3,2,1];
let  sequentialSearch = function (item,arr){
  for(let i = 0; i < arr.length; i++){
    if(item === arr[i]){
        return i;
    }
  }
  return -1;
}
let res = sequentialSearch(3,arr);
console.log(res);

上面的算法中如果找到了搜索项，就会返回搜索项的下标，如果没有找到该项，就会返回-1，表示索引不存在，当然也可以考虑返回null或是false。

顺序查找的示意图

二分搜索

二分搜索的做法的原理有一点类似于猜数字的游戏，就是有一个人说：我想到了一个1到100中的数字，我们没回应一个数字，那个人就会回应说这个数字是高了、低了、还是对了。
这个算法有一个要求，就是这个被搜索的数据结构已经排序了，下面是这个算法需要遵循的步骤：
(1)选择数组的中间值
(2)如果选中值是待搜索值，那么算法就执行完毕了(值找到了)。
(3)如果待搜索值比选中值小，就返回步骤1并在选中值左边的子数组中查找。
(4)如果待搜索值比选中值大，就返回步骤1并在选中值右边的子数组中查找。

let arr2 = [10,9,8,7,6,5,4,3,2,1];
let binarySearch = function (item,arr){
    let low = 0;
    high = arr2.length - 1;
    let middle,curElement;
    while(low <= high){
        middle = Math.floor((low+high)/2);
        curElement = arr2[middle];
        if(curElement < item){
            low = middle + 1;
        }else if(curElement > item){
            high = middle -1;
        }else{
            return middle
        }
    }
    return -1;
};
let res = sequentialSearch(2,arr2);
console.log(res);

二分查找的示意图