常用的JS搜索算法有哪些

这篇文章主要介绍“常用的JS搜索算法有哪些”，在日常操作中，相信很多人在常用的JS搜索算法有哪些问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”常用的JS搜索算法有哪些”的疑惑有所帮助！接下来，请跟着小编一起来学习吧！

1.for循环搜索

• 基本思路：通过for循环遍历数组，找出要搜索的值在数组中的索引，并将其推进新数组

代码实现如下：

const getFnRunTime = require('./getRuntime');   /**   * 普通算法-for循环版   * @param {*} arr    * 耗时：7-9ms   */  function searchBy(arr, value) {      let result = [];     for(let i = 0, len = arr.length; i < len; i++) {         if(arr[i] === value) {             result.push(i);         }     }     return result  }  getFnRunTime(searchBy, 6)

测试n次稳定后的结果如图：

 

2.forEach循环

基本思路和for循环类似：

/**   * 普通算法-forEach循环版   * @param {*} arr    * 耗时：21-24ms   */  function searchByForEach(arr, value) {     let result = [];     arr.forEach((item,i) => {         if(item === value) {             result.push(i);         }     })    return result }

耗时21-24毫秒，可见性能不如for循环(先暂且这么说哈，本质也是如此)。

3.while循环

代码如下：

/**   * 普通算法-while循环版   * @param {*} arr    * 耗时：11ms   */  function searchByWhile(arr, value) {      let i = arr.length,      result = [];     while(i) {         if(arr[i] === value) {             result.push(i);         }         i--;     }         return result }

可见while和for循环性能差不多，都很优秀，但也不是说forEach性能就不好，就不使用了。foreach相对于for循环，代码减少了，但是foreach依赖IEnumerable。在运行时效率低于for循环。但是在处理不确定循环次数的循环，或者循环次数需要计算的情况下，使用foreach比较方便。而且foreach的代码经过编译系统的代码优化后，和for循环的循环类似。

4.二分法搜索

二分法搜索更多的应用场景在数组中值唯一并且有序的数组中，这里就不比较它和for/while/forEach的性能了。

• 基本思路：从序列的中间位置开始比较，如果当前位置值等于要搜索的值，则查找成功;若要搜索的值小于当前位置值，则在数列的前半段中查找;若要搜索的值大于当前位置值则在数列的后半段中继续查找，直到找到为止

代码如下：

/**    * 二分算法    * @param {*} arr     * @param {*} value     */   function binarySearch(arr, value) {     let min = 0;     let max = arr.length - 1;          while (min <= max) {       const mid = Math.floor((min + max) / 2);          if (arr[mid] === value) {         return mid;       } else if (arr[mid] > value) {         max = mid - 1;       } else {         min = mid + 1;       }     }        return 'Not Found';   }

在数据量很大的场景下，二分法效率很高，但不稳定，这也是其在大数据查询下的一点小小的劣势。

5.哈希表查找

• 哈希表查找又叫散列表查找，通过查找关键字不需要比较就可以获得需要记录的存储位置，它是通过在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使得每个关键字key对应一个存储位置f(key)

哈希表查找的使用场景：

• 哈希表最适合的求解问题是查找与给定值相等的记录

• 哈希查找不适合同样的关键字对应多条记录的情况

• 不适合范围查找，比如查找年龄18~22岁的同学

在这我先给出一个最简版的hashTable，方便大家更容易的理解哈希散列：

/**  * 散列表  * 以下方法会出现数据覆盖的问题  */ function HashTable() {   var table = [];    // 散列函数   var loseloseHashCode = function(key) {     var hash = 0;     for(var i=0; i<key.length; i++) {       hash += key.charCodeAt(i);     }     return hash % 37   };    // put   this.put = function(key, value) {     var position = loseloseHashCode(key);     table[position] = value;   }    // get   this.get = function(key) {     return table[loseloseHashCode(key)]   }    // remove   this.remove = function(key) {     table[loseloseHashCode(key)] = undefined;   } }

该方法可能会出现数据冲突的问题，不过也有解决方案，由于这里涉及的知识点比较多，后期我会专门推出一篇文章来介绍：

• 开放定址法

• 二次探测法

• 随机探测法

使用web worker优化

通过以上的方法，我们已经知道各种算法的性能和应用场景了，我们在使用算法时，还可以通过web  worker来优化，让程序并行处理，比如将一个大块数组拆分成多块，让web  worker线程帮我们去处理计算结果，最后将结果合并，通过worker的事件机制传给浏览器，效果十分显著。

到此，关于“常用的JS搜索算法有哪些”的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注亿速云网站，小编会继续努力为大家带来更多实用的文章！