搜索查找

参考：

• https://juejin.cn/post/6844903866610221064
• https://www.hello-algo.com/chapter_searching/

查找和排序都是在程序设计当中经常用到的算法。查找相对而言较为简单，排序比查找要复杂一些。查找有顺序查找（线性查找）、二分查找、哈希查找、二叉排序树查找等方法。

线性查找

时间复杂度至少为 O(n)，根据遍历次数复杂度可能会增加。
空间复杂度至少为 O(1)，根据使用空间复杂度可能会增加。

for 循环

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

/**
 * 普通算法-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;
}

forEach 循环

基本思路和 for 循环类似，但性能不如 for 循环：

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

while 循环

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

/**
 * 普通算法-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;
}

二分查找

二分查找是一种基于分治策略的高效搜索算法，场景更多应用在值唯一并且有序的数组中。从序列的中间位置开始比较，如果当前位置值等于要搜索的值，则查找成功；若要搜索的值小于当前位置值，则在数列的前半段中查找；若要搜索的值大于当前位置值则在数列的后半段中继续查找，直到找到：

/**
 * 二分算法
 * @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";
}

时间复杂度为 O(logn) ：在二分循环中，区间每轮缩小一半，因此循环次数为 log₂n。
空间复杂度为 O(1) ：指针 min 和 max 使用常数大小空间。

优点与局限性

二分查找在时间和空间方面都有较好的性能：

• 二分查找的时间效率高。在大数据量下，对数阶的时间复杂度具有显著优势
• 二分查找无须额外空间。相较于需要借助额外空间的搜索算法（如哈希查找），二分查找更省空间

然而，二分查找并非适用于所有情况，主要有以下原因：

• 二分查找仅适用于有序数据。若输入数据无序，为了使用二分查找而专门进行排序，得不偿失。因为排序算法的时间复杂度通常为 O(nlogn)，比线性查找和二分查找都更高。对于频繁插入元素的场景，为保持数组有序性，需要将元素插入到特定位置，时间复杂度为 O(n)，也是非常昂贵的
• 二分查找仅适用于数组。二分查找需要跳跃式（非连续地）访问元素，但是在链表中执行跳跃式访问的效率较低，因此不适合应用在链表或基于链表实现的数据结构
• 小数据量时线性查找性能更佳。在线性查找中，每轮只需 1 次判断操作；而在二分查找中，需要 1 次加法、1 次除法、1 ~ 3 次判断操作、1 次加法（减法），共 4 ~ 6 个单元操作；所以当数据量较小时，线性查找反而比二分查找更快

哈希查找

常通过将线性查找替换为哈希查找来降低算法的时间复杂度：

• 考虑直接遍历所有可能的组合，线性查找是以时间换空间
• 考虑借助一个哈希表，键值对分别为数组元素和元素索引，哈希查找是以空间换时间

给定一个整数数组 nums 和一个目标元素 target ，请在数组中搜索“和”为 target 的两个元素，并返回它们的数组索引。返回任意一个解即可。

// 线性查找
function fun1(arr, target) {
  for (let i = 0; i < arr.legnth; i++) {
    const num1 = arr[i];
    for (let j = i + 1; j < arr.length; j++) {
      const num2 = arr[j];
      if (num1 + num2 === target) {
        return [i, j];
      }
    }
  }
}

// 哈希查找
function fun2(arr, target) {
  const m = {};
  for (let i = 0; i < arr.length; i++) {
    if (target - arr[i] !== undefined) {
      return [i, m[target - arr[i]]];
    } else {
      m[arr[i]] = i;
    }
  }
}

总结

搜索算法用于在数据结构（例如数组、链表、树或图）中搜索一个或一组满足特定条件的元素。搜索算法可根据实现思路分为以下两类：

• 通过遍历数据结构来定位目标元素，例如数组、链表、树和图的遍历等
• 利用数据组织结构或数据包含的先验信息，实现高效元素查找，例如二分查找、哈希查找和二叉搜索树查找等