十五、搜索
访问 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
