十五、搜索

访问 www.coding-time.cn 阅读原文动画效果，体验更佳。

1. 二分查找

在计算机科学中，二分查找（Binary Search），也称为折半查找、对数查找或二分法，是一种用于在有序数组中查找目标值位置的搜索算法。二分查找将目标值与数组的中间元素进行比较；如果它们不相等，则可以排除目标值不可能存在的一半，并在剩余的一半上继续搜索，直到找到目标值或搜索结束。如果搜索结束时剩余的一半为空，则表示数组中不存在目标值。

1）复杂度

时间复杂度：O(log(n)) - 因为每次迭代都将搜索区域分成两半。

2）完整实现

function binarySearch(array, target) {
  let left = 0;
  let right = array.length - 1;
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    if (array[mid] === target) {
      return mid; // 找到目标元素，返回索引
    } else if (array[mid] < target) {
      left = mid + 1; // 目标元素在右侧，调整左边界
    } else {
      right = mid - 1; // 目标元素在左侧，调整右边界
    }
  }
  return -1; // 未找到目标元素}

3）参考资料

• 维基百科
  
• YouTube
  

2.插值查找

插值查找（Interpolation Search）是一种用于在已按键（键值）排序的数组中搜索键的算法。

例如，我们有一个排序的数组 arr[]，其中包含 n 个均匀分布的值，并且我们需要编写一个函数在数组中搜索特定元素 x。

线性搜索的时间复杂度为 O(n)，跳跃搜索的时间复杂度为 O(√n)，二分查找的时间复杂度为 O(logn)。

插值查找是对二分查找的改进，适用于在已排序数组中元素的分布是“均匀”的情况。二分查找总是检查中间元素。而插值查找根据所搜索的键的值可能接近的位置进行搜索。例如，如果键的值更接近最后一个元素，则插值查找可能从末尾开始搜索。

要找到要搜索的位置，它使用以下公式：

// 这个公式的思想是，当要搜索的元素更接近 arr[hi] 时，返回较大的 pos 值。
// 当更接近 arr[lo] 时，返回较小的值。
pos = lo + ((x - arr[lo]) * (hi - lo) / (arr[hi] - arr[lo]))
arr[] - 需要进行搜索的数组
x - 要搜索的元素
lo - arr[] 中的起始索引
hi - arr[] 中的结束索引

1）复杂度

时间复杂度：O(log(log(n)))

带你读《图解算法小抄》十五、搜索（2）https://developer.aliyun.com/article/1348121?groupCode=tech_library