JavaScript 数据结构与算法之检索算法

什么是检索算法

检索算法，也称为查找算法，是解决在数据集合中寻找某个特定元素的算法。

比如，在一个给定的数组中查找特定的元素，或者在一个字典中查找某个特定单词的定义等等，这些都是检索算法的应用场景。

JavaScript 中的检索算法主要有以下几种：线性查找、二分查找、哈希查找。

线性查找

线性查找，也叫顺序查找，是最简单的一种查找算法。它的基础思想是从序列中的第一个元素开始比较，直到找到或者搜索完整个序列为止。

以下是线性查找的 JavaScript 代码实现：

function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) {
      return i;
    }
  }
  return -1;
}

const arr = [85, 24, 63, 45, 17, 31, 96, 50];
const target = 31;
const result = linearSearch(arr, target);
console.log(result); // 5

上述代码中，linearSearch 函数接受两个参数：一个数组 arr 和一个目标元素 target。依次遍历数组中的每一个元素，如果找到了目标元素，就返回对应的索引位置。如果找遍了整个数组都没有找到目标元素，就返回 -1。

二分查找

二分查找，也称为折半查找，是一种非常高效的检索算法。它的基础思想是将有序的数据集合分成两部分，每次查找都根据中间位置的值与目标值的大小关系来确定待查找的区间，在缩小范围中继续查找，直到找到目标值为止。

以下是二分查找的 JavaScript 代码实现：

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) {
      return mid;
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return -1;
}

const arr = [17, 24, 31, 45, 50, 63, 85, 96];
const target = 31;
const result = binarySearch(arr, target);
console.log(result); // 2

上述代码中， binarySearch 函数接受两个参数：一个有序数组 arr 和一个目标元素 target。首先初始化两个指针 left 和 right 分别指向数组的最左端和最右端，然后通过计算中间指针的位置 mid 来将数组分成两部分。如果中间指针所指的数等于目标元素，则找到了目标元素，返回对应的索引位置。如果中间指针所指的数小于目标元素，则将 left 位置更新为 mid + 1。如果中间指针所指的数大于目标元素，则将 right 位置更新为 mid - 1。重复上述过程，直到找到目标元素或者遍历整个数组为止。

示例说明

示例一：线性查找

const arr = [85, 24, 63, 45, 17, 31, 96, 50];
const target = 31;
const result = linearSearch(arr, target);
console.log(result); // 5

上述代码实现了线性查找算法，要查找的目标元素是 31，在数组中的索引位置是 5。

示例二：二分查找

const arr = [17, 24, 31, 45, 50, 63, 85, 96];
const target = 31;
const result = binarySearch(arr, target);
console.log(result); // 2

上述代码实现了二分查找算法，要查找的目标元素是 31，在数组中的索引位置是 2。

总结

检索算法是解决在数据集合中寻找某个特定元素的算法，JavaScript 中的检索算法主要有：线性查找、二分查找和哈希查找。其中，线性查找是最简单的一种算法，适用于规模较小的数据集合；而二分查找是一种高效的查找算法，时间复杂度较低，适用于大规模有序数据的查找。根据具体场景选择不同的检索算法能够提高算法效率，提高代码的执行效率。