关于程序员:前端开发应该掌握的查找算法

前端开发人员在平时我的项目开发过程中查找算法应该是应用频率最高的算法之一，因而咱们把握一些常见的查找算法是很有必要的，把握这些算法不仅能进步咱们的开发工作效率，好的算法实现还能在肯定水平上晋升我的项目性能，同时也能晋升咱们的编程思维能力。

那么常见的查找算法有哪些呢？

线性查找
二分查找
插值查找
哈希查找
二叉搜寻树查找
AVL 树、红黑树、B 树 /B+ 树查找
总结

线性查找（Linear Search）是一种简略直观的查找算法，实用于无序的数据汇合。它通过一一比拟查找指标，直到找到指标元素或遍历残缺个数据汇合。

实现原理：

从数据汇合的第一个元素开始，一一与指标元素进行比拟。
如果找到了匹配的元素，返回该元素的索引。
如果遍历残缺个数据汇合都没有找到匹配的元素，返回 - 1 示意查找失败。

示例代码和正文如下：

// 线性查找算法
function linearSearch(arr, target) {for (let i = 0; i < arr.length; i++) {if (arr[i] === target) {return i; // 返回匹配元素的索引}
  }
  return -1; // 没有找到匹配元素，返回 -1
}

// 示例用法
const arr = [5, 8, 2, 10, 3];
const target = 10;
const index = linearSearch(arr, target);
console.log(index); // 输入：3

应用场景：
线性查找实用于简略的无序数据汇合，或者数据汇合规模较小的状况。它不须要数据汇合有特定的排序形式，能够间接遍历查找指标元素。线性查找的长处是简略易懂，实现简略，对于小规模数据汇合的查找是无效的。然而，对于大规模数据汇合，线性查找的效率绝对较低，因为它的工夫复杂度为 O(n)，须要一一比拟所有元素。在须要频繁进行查找操作、数据汇合较大且有序的状况下，能够思考应用其余更高效的查找算法，如二分查找或哈希查找。

二分查找（Binary Search）是一种高效的查找算法，实用于有序的数据汇合。它通过将查找范畴分成两半，并与指标元素进行比拟，从而疾速定位指标元素的地位。

实现原理：

确定查找范畴的起始地位（通常是数组的起始地位和完结地位）。
计算查找范畴的两头地位。
将两头地位的元素与指标元素进行比拟。
如果两头地位的元素与指标元素相等，示意找到指标元素，返回两头地位的索引。
如果两头地位的元素大于指标元素，放大查找范畴为左半局部，继续执行步骤 2。
如果两头地位的元素小于指标元素，放大查找范畴为右半局部，继续执行步骤 2。
如果查找范畴放大到起始地位大于完结地位，示意未找到指标元素，返回 - 1 示意查找失败。

示例代码和正文如下：

// 二分查找算法
function binarySearch(arr, target) {
  let start = 0; // 起始地位
  let end = arr.length - 1; // 完结地位

  while (start <= end) {let mid = Math.floor((start + end) / 2); // 两头地位

    if (arr[mid] === target) {return mid; // 找到指标元素，返回索引} else if (arr[mid] > target) {end = mid - 1; // 放大查找范畴为左半局部} else {start = mid + 1; // 放大查找范畴为右半局部}
  }

  return -1; // 未找到指标元素，返回 -1
}

// 示例用法
const arr = [2, 5, 8, 10, 15];
const target = 8;
const index = binarySearch(arr, target);
console.log(index); // 输入：2

应用场景：
二分查找实用于有序的数据汇合。相较于线性查找，二分查找具备更高的效率，因为它通过将查找范畴放大一半来迅速定位指标元素。二分查找的工夫复杂度为 O(log n)。应用二分查找的前提是数据汇合曾经有序，因而实用于静态数据汇合或者很少变动的数据汇合。常见的应用场景包含查找有序数组、在数据库索引中进行查找、在字典或词汇表中进行查找等。然而，二分查找的局限是要求数据汇合必须有序，如果数据汇合频繁变动，插入和删除元素时须要维持有序性，可能会导致插入和删除操作的效率降落。

插值查找（Interpolation Search）是一种优化的查找算法，特地实用于有序且均匀分布的数据汇合。它通过估算指标元素所在的地位，从而更快地定位指标元素。

实现原理：

确定查找范畴的起始地位和完结地位。
依据指标元素的估算地位，计算出一个估算索引（插值公式）。
比拟估算索引处的元素与指标元素的大小关系。
如果估算索引处的元素等于指标元素，示意找到指标元素，返回估算索引。
如果估算索引处的元素大于指标元素，放大查找范畴为估算索引的左侧，继续执行步骤 2。
如果估算索引处的元素小于指标元素，放大查找范畴为估算索引的右侧，继续执行步骤 2。
如果查找范畴放大到起始地位大于完结地位，示意未找到指标元素，返回 - 1 示意查找失败。

示例代码和正文如下：

// 插值查找算法
function interpolationSearch(arr, target) {
  let start = 0; // 起始地位
  let end = arr.length - 1; // 完结地位

  while (start <= end && target >= arr[start] && target <= arr[end]) {
    // 依据指标元素的估算地位计算估算索引
    let pos = start + Math.floor(((target - arr[start]) / (arr[end] - arr[start])) * (end - start));

    if (arr[pos] === target) {return pos; // 找到指标元素，返回索引} else if (arr[pos] < target) {start = pos + 1; // 放大查找范畴为估算索引的右侧} else {end = pos - 1; // 放大查找范畴为估算索引的左侧}
  }

  return -1; // 未找到指标元素，返回 -1
}

// 示例用法
const arr = [2, 5, 8, 10, 15];
const target = 8;
const index = interpolationSearch(arr, target);
console.log(index); // 输入：2

应用场景：
插值查找实用于有序且均匀分布的数据汇合。相较于二分查找，插值查找通过更精准地估算指标元素的地位，能够在有序数据汇合中更快地定位指标元素。插值查找的工夫复杂度均匀状况下为 O(log log n)，最坏状况下为 O(n)，但通常状况下比二分查找效率更高。应用插值查找的前提是数据汇合有序且散布平均，这样能力更精确地估算指标元素的地位。常见的应用场景包含有序数组的查找和索引、数值范畴查找等。然而，插值查找的局限性在于对于散布不平均的数据汇合，可能导致查找性能的降落，甚至无奈达到预期的成果。因而，在抉择插值查找算法时，须要依据数据汇合的特点进行评估。

哈希查找（Hash Search）是一种基于哈希表的查找算法，通过将元素映射到哈希表中的索引地位来进行查找。哈希查找具备疾速的查找速度，实用于大规模数据汇合和须要频繁查找的场景。

实现原理：

创立一个哈希表（也能够应用 JavaScript 中的对象来模仿哈希表）。
遍历数据汇合，将每个元素通过哈希函数映射到哈希表的索引地位，并将元素存储在该地位。
当须要查找指标元素时，将指标元素通过哈希函数计算出对应的索引地位。
在哈希表中查看该索引地位是否存在元素，如果存在且与指标元素相等，则示意找到指标元素。
如果哈希表中的该索引地位没有元素，或者存在元素但不等于指标元素，则示意未找到指标元素。

示例代码和正文如下：

// 应用函数哈希查找算法
function hashSearch(arr, target) {const hashTable = {}; // 哈希表

  // 构建哈希表
  for (let i = 0; i < arr.length; i++) {hashTable[arr[i]] = i;
  }

  // 查找指标元素
  if (hashTable.hasOwnProperty(target)) {return hashTable[target]; // 找到指标元素，返回索引
  }

  return -1; // 未找到指标元素，返回 -1
}

// 示例用法
const arr = [5, 8, 2, 10, 3];
const target = 10;
const index = hashSearch(arr, target);
console.log(index); // 输入：3  留神：该实现如果有反复数据，则会取最初一个元素的索引

实现原理：

创立一个哈希表，用于存储数据。
定义一个哈希函数，它将键映射为哈希值，该哈希值示意键的存储地位。
将键值对插入到哈希表中，依据哈希函数计算键的哈希值，并将值存储在对应的哈希地位。
当须要查找键对应的值时，应用哈希函数计算键的哈希值，而后在哈希表中查找对应的存储地位，获取值。

// 应用类实现哈希查找算法
class HashTable {constructor() {this.table = {}; // 哈希表，用对象示意
  }

  // 哈希函数，将键转换为哈希值
  hash(key) {
    let hashValue = 0;
    for (let i = 0; i < key.length; i++) {hashValue += key.charCodeAt(i);
    }
    return hashValue % 37; // 取余数作为哈希值
  }

  // 插入键值对到哈希表中
  insert(key, value) {const index = this.hash(key);
    this.table[index] = value;
  }

  // 依据键查找值
  search(key) {const index = this.hash(key);
    return this.table[index];
  }
}

// 示例用法
const hashTable = new HashTable();
hashTable.insert("apple", "red");
hashTable.insert("banana", "yellow");
const value = hashTable.search("apple");
console.log(value); // 输入：red  留神：该实现如果有反复插入数据，则会取最初一个元素

应用场景：
哈希查找实用于大规模数据汇合和须要频繁查找的场景。它的查找速度快，均匀状况下的工夫复杂度为 O(1)，即常数工夫。哈希查找在解决海量数据时具备较高的效率，适宜用于数据库索引、缓存零碎、字典等须要疾速查找的场景。然而，哈希查找也有一些局限性，如哈希函数设计不当可能导致哈希抵触，须要解决抵触的办法（如链表法或凋谢地址法），并且哈希表须要额定的空间来存储元素。另外，哈希查找对数据汇合的有序性没有要求，实用于无序数据汇合。因而，在抉择哈希查找算法时，须要依据理论利用场景综合思考。

二叉搜寻树（Binary Search Tree，BST）是一种罕用的数据结构，具备高效的查找操作。它满足以下性质：

每个节点最多有两个子节点，称为左子节点和右子节点。
左子节点的值小于父节点的值，右子节点的值大于父节点的值。
对于每个节点，其左子树中的所有节点值都小于该节点的值，右子树中的所有节点值都大于该节点的值。

实现原理：

创立一个二叉搜寻树，并初始化为空树。
将第一个元素作为根节点插入到树中。
对于要插入的新元素，从根节点开始比拟其值与以后节点的值的大小关系。
如果新元素的值小于以后节点的值，则将其插入到以后节点的左子树中。
如果新元素的值大于以后节点的值，则将其插入到以后节点的右子树中。
反复步骤 3 -5，直到找到适合的插入地位（即遇到空节点）。
查找元素时，从根节点开始比拟要查找的元素与以后节点的值的大小关系。
如果要查找的元素等于以后节点的值，则找到指标元素。
如果要查找的元素小于以后节点的值，则持续在以后节点的左子树中查找。
如果要查找的元素大于以后节点的值，则持续在以后节点的右子树中查找。
如果找到指标元素或遇到空节点，则完结查找。

示例代码和正文如下：

// 二叉搜寻树节点类
class Node {constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

// 二叉搜寻树类
class BinarySearchTree {constructor() {this.root = null; // 根节点}

  // 插入元素
  insert(value) {const newNode = new Node(value); // 创立新节点

    // 如果根节点为空，则将新节点作为根节点
    if (this.root === null) {this.root = newNode;} else {this.insertNode(this.root, newNode); // 插入节点
    }
  }

  // 辅助函数：递归插入节点
  insertNode(node, newNode) {
    // 如果新节点的值小于以后节点的值，则将其插入到左子树中
    if (newNode.value < node.value) {if (node.left === null) {node.left = newNode;} else {this.insertNode(node.left, newNode);
      }
    }
    // 如果新节点的值大于以后节点的值，则将其插入到右子树中
    else {if (node.right === null) {node.right = newNode;} else {this.insertNode(node.right, newNode);
      }
    }
  }

 

 // 查找元素
  search(value) {return this.searchNode(this.root, value); // 从根节点开始查找
  }

  // 辅助函数：递归查找节点
  searchNode(node, value) {
    // 如果节点为空，示意未找到指标元素
    if (node === null) {return false;}
    // 如果指标元素等于以后节点的值，示意找到指标元素
    if (value === node.value) {return true;}
    // 如果指标元素小于以后节点的值，则持续在左子树中查找
    if (value < node.value) {return this.searchNode(node.left, value);
    }
    // 如果指标元素大于以后节点的值，则持续在右子树中查找
    else {return this.searchNode(node.right, value);
    }
  }
}

// 示例用法
const bst = new BinarySearchTree();
bst.insert(5);
bst.insert(8);
bst.insert(2);
bst.insert(10);
bst.insert(3);

console.log(bst.search(10)); // 输入：true
console.log(bst.search(7)); // 输入：false

应用场景：
二叉搜寻树实用于须要疾速查找和插入的状况，尤其在动态数据汇合中，它具备较高的查找效率。二叉搜寻树的查找、插入、删除的均匀工夫复杂度是 O(log n)，其中 n 是树中节点的数量。

常见的应用场景包含：

数据的动静插入和删除：二叉搜寻树能够高效地插入和删除节点，放弃树的有序性。
排序：通过对二叉搜寻树进行中序遍历，能够失去有序的数据序列。
查找最大值和最小值：二叉搜寻树的最左子节点是最小值，最右子节点是最大值。
区间查问：通过在二叉搜寻树上进行范畴查找，能够找到满足特定区间条件的节点。

请留神，二叉搜寻树的性能受树的均衡水平影响，如果树过于歪斜，可能会导致查找性能降落，因而在理论应用时，须要思考均衡二叉搜寻树（如 AVL 树、红黑树等）来维持树的平衡性。

AVL 树、红黑树和 B 树 /B+ 树都是常见的自均衡二叉搜寻树，它们在解决大量数据和保护平衡性方面具备劣势。

AVL 树:
- AVL 树是一种严格均衡的二叉搜寻树，它通过在每个节点上保护一个均衡因子（左子树高度减去右子树高度）来保持平衡。
- 均衡因子的绝对值不能超过 1，即每个节点的左子树和右子树的高度差不超过 1。
- 插入和删除操作可能须要通过旋转操作来从新均衡树。
- AVL 树实用于须要疾速的查找和更新操作，并对树的平衡性要求较高的场景。
红黑树:
- 红黑树是一种近似均衡的二叉搜寻树，它通过在每个节点上引入额定的色彩属性（红色或彩色）来保持平衡。
- 红黑树具备以下性质：
  1) 每个节点要么是红色，要么是彩色。
  2) 根节点是彩色。
  3) 每个叶子节点（NIL 节点，空节点）是彩色。
  4) 如果一个节点是红色，则它的两个子节点都是彩色。
  5) 从任意节点到其每个叶子节点的门路上，蕴含雷同数量的彩色节点。
- 红黑树通过色彩变换和旋转操作来保持平衡。
- 红黑树实用于须要高效的插入、删除和查找操作，并对树的平衡性要求适度的场景。
B 树 /B+ 树:
- B 树和 B + 树是多路搜寻树，每个节点能够蕴含多个键值和子节点。
- B 树是一种均衡的树结构，它具备以下特点：
  1) 根节点至多有两个子节点。
  2) 每个两头节点（非叶子节点）都蕴含 k 个子节点和 k - 1 个键值，其中 t <= k <= 2t，t 为最小度数。
  3) 所有叶子节点位于同一层级。
- B+ 树是 B 树的变种，它在 B 树的根底上做了一些优化：
  1) 所有的键值都在叶子节点中呈现，两头节点只蕴含键值的正本。
  2) 叶子节点通过指针链接起来，造成一个有序链表。
- B 树和 B + 树实用于大规模数据的索引构造，例如数据库和文件系统索引。

这些自均衡二叉搜寻树都具备较好的均衡性能和高效的插入、删除和查找操作，但每种树在不同场景下具备不同的特点和适用性。在抉择应用哪种树构造时，须要依据具体的利用需要和数据规模进行综合思考。

AVL 树、红黑树、B 树 /B+ 树查找这些工作当中根本用不到，而且实现起来比较复杂，理解即可。

查找算法作为程序员编码开发中应用最多的一种算法，把握像线性查找、二分查找、插值查找、哈希查找算法，根本能够笼罩平时开发中绝大多数场景了，至于最初章节提到 AVL 树、红黑树、B 树 /B+ 树等自均衡二叉搜寻树，因为实现复杂度比拟高，而且对性能要求特地高的场景才会应用到，因而大抵理解即可，感兴趣的能够自行把握。把握 JS 中的常见的查找算法能够进步数据处理和查问的效率，优化算法和数据结构的实现，并解决各种理论问题，这对于开发人员来说是十分有用的技能。

本文由 mdnice 多平台公布

关于程序员:前端开发应该掌握的查找算法

前端开发应该把握的查找算法

线性查找

二分查找

插值查找

哈希查找

应用函数实现哈希查找算法

应用类实现哈希查找算法

二叉搜寻树

AVL 树、红黑树、B 树 /B+ 树查找

总结