0


JavaScript 中常见的搜索算法

线性搜索

线性搜索是一种常见的搜索算法,它接受一个数组和一个值 - 并返回该值所在的索引。如果该值不存在,该函数将返回 -1。实施:

  1. 从从 i 开始并遍历数组长度的 for 循环开始
  2. 检查当前数组元素是否等于给定值。
  3. 如果找到,则返回该值的索引
  4. 如果值不存在,则返回 -1 代码如下:
function linearSearch(arr, val){
    for(let i = 0; i < arr.length; i++){
        if(arr[i] === val) return i;
    }
    return -1;
}

该函数的平均和最差时间复杂度为 O(N),最佳情况时间复杂度为 O(1)。我们的下一个搜索算法将改进这个时间复杂度。

二进制搜索

二进制搜索是一种比线性搜索更有效的算法,但需要注意的是它仅适用于已排序的数组。实施:

  1. 创建一个接受排序数组和值的函数。
  2. 在数组的开头创建一个左指针,在数组的末尾创建一个右指针。
  3. 当左指针在右指针前面时: - 在数组中间创建一个指针。您可以通过取起始值和结束值的平均值并使用 Math.floor() 来确保一个四舍五入的数字来找到这个中间值- 如果找到匹配值,则返回索引- 如果值太小,将左指针向上移动- 如果值太大,将右指针向下移动- 继续此过程,直到找到正确的值
  4. 如果该值不存在,则返回 -1

代码如下:

function binarySearch(arr, elem) {
    let start = 0;
    let end = arr.length - 1;
    let middle = Math.floor((start + end) / 2);
    while(arr[middle] !== elem && start <= end) {
        if(elem < arr[middle]) end = middle - 1;
        else start = middle + 1;
        middle = Math.floor((start + end) / 2);
    }
    return arr[middle] === elem ? middle : -1;
}

记住!此方法仅适用于排序数组!但是,如果您确实有一个排序数组,那么与线性搜索相比,时间复杂度会大大提高。最差和平均时间复杂度为 O(log n),最佳情况为 O(1)。

简单字符串搜索

我将介绍的最终搜索算法是简单字符串搜索。该算法对于在较大的字符串中查找模式很有用。例如,您可以尝试找出“AABA”在字符串“AABAACAADAABAABA”中出现的次数。实施:

  1. 定义一个函数,该函数接受一个较大的字符串,然后是包含您要查找的模式的字符串
  2. 循环较长的字符串
  3. 在该循环中,循环较短/模式字符串
  4. 检查匹配 - 如果您找到匹配项,请继续- 如果你找到一个完整的匹配,增加你的匹配计数
  5. 如果未找到匹配项,则跳出内部循环
  6. 返回最后的总数

代码如下:

function naiveSearch(long, short){
  let count = 0;
  for(let i = 0; i < long.length; i++){
    for(let j = 0; j < short.length; j++){
      if(short[j] !== long[i+j]) break;
      if(j === short.length - 1) count++;
      }
    }
 return count;
}

简单字符串搜索的最佳情况时间复杂度是 O(n)。最坏的情况是 O(m*(n-m+1))。


本文转载自: https://blog.csdn.net/qq_39606853/article/details/125268005
版权归原作者 前端e站 所有, 如有侵权,请联系我们删除。

“JavaScript 中常见的搜索算法”的评论:

还没有评论