二分查找
二分查找
基础知识
二分查找，英语为 Binary Search，这是一种高效的 查找 算法，适用于在 已排序 的数组中快速定位目标元素。其核心思想是通过每次将查找范围缩小一半，逐步逼近目标值，从而实现快速查找。
1-100 之间想好了一个数，来猜这个数，每次猜测后，我会告诉你大了还是小了。
- 50 ？大了
- 25 ？
- ....
二分查找的基本步骤如下：
-
初始化查找区间： 设置两个指针，
left和right，分别指向数组的起始和结束位置。 -
计算中间位置： 在每次查找中，计算当前查找区间的中间索引 mid，通常使用
Math.floor((left + right) / 2)来避免浮点数误差。 -
比较中间元素与目标值：
- 如果
arr[mid]等于目标值，则查找成功，返回mid - 如果
arr[mid]小于目标值，则目标值位于右半部分，更新left = mid + 1 - 如果
arr[mid]大于目标值，则目标值位于左半部分，更新right = mid - 1
- 如果
-
重复上述过程： 直到找到目标值或 left 超过 right，表示查找失败，返回 -1
代码实现
- 迭代实现
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
// 可以进行查找
// 根据 left 和 right 计算出中间的下标
const mid = Math.floor((left + right) / 2);
// 中间下标所对应的元素和目标值进行比较
if (arr[mid] === target) {
// 说明找到了
return mid;
} else if (arr[mid] < target) {
// 目标值在右半部分区域，更新 left
left = mid + 1;
} else {
// 目标值在左半部分区域，更新 right
right = mid - 1;
}
}
// 思考：什么时候退出 while
// 当 left 大于 right 的时候，会退出 while
// 说明没有找到
return -1;
}
const arr = [4, 7, 9, 11, 20, 24, 30, 41];
const target1 = 30;
const target2 = 70;
console.log(binarySearch(arr, target1)); // 6
console.log(binarySearch(arr, target2)); // -1
- 递归实现
function binarySearch(arr, target, left = 0, right = arr.length - 1) {
if (left > right) {
// 没有找到时递归的出口
return -1;
}
const mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
// 找到的时候，递归的出口
return mid;
} else if (arr[mid] < target) {
// 说明目标值在右边
return binarySearch(arr, target, mid + 1, right);
} else {
// 说明目标值在左边
return binarySearch(arr, target, left, mid - 1);
}
}
const arr = [4, 7, 9, 11, 20, 24, 30, 41];
const target1 = 30;
const target2 = 70;
console.log(binarySearch(arr, target1)); // 6
console.log(binarySearch(arr, target2)); // -1
复杂度
- 时间复杂度：
O(logn)因为每一次查找的区间都缩小一半，每次缩小的程度是对数级别。 - 空间复杂度：
- 迭代实现：
O(1) - 递归实现：
O(logn)因为每一次递归都会占用一定的空间。
- 迭代实现：
-EOF-
二分查找
http://localhost:8090/archives/er-fen-cha-zhao