二分法查找 js

二分法查找是一种常用的算法，在 JavaScript 中也有其应用。本文将从以下几个方面进行分析：什么是二分法查找；为什么要使用二分法查找；二分法查找的实现方法；二分法查找的时间复杂度分析。

什么是二分法查找

二分法查找也被称为折半查找，它是一种针对有序数组的搜索算法。具体来说，二分法查找从数组的中间元素开始，如果中间元素正好是目标值，则搜索过程结束；如果目标值大于或小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟中间元素比较一遍，重复此过程，直到找到目标值或者数组为空。

为什么要使用二分法查找

二分法查找的时间复杂度为 O(log n)，n 是数组的长度。相比于线性查找的时间复杂度 O(n)，二分法查找的速度更快。因此，在需要快速检索有序数组的情况下，二分法查找是一种非常有效的算法。

二分法查找的实现方法

在 JavaScript 中，我们可以使用递归或迭代的方式实现二分法查找。下面是使用递归方式实现的代码示例：

```

function binarySearch(arr, target, left = 0, right = arr.length - 1) {

if (left > right) return -1; // 没有找到目标值，返回 -1

const mid = Math.floor((left + right) / 2);

if (arr[mid] === target) return mid; // 找到目标值，返回下标

else if (arr[mid] > target) return binarySearch(arr, target, left, mid - 1); // 在左半部分查找

else return binarySearch(arr, target, mid + 1, right); // 在右半部分查找

}

```

使用迭代方式实现的代码示例：

```

function binarySearch(arr, target) {

let left = 0;

let right = arr.length - 1;

while (left <= right) {

const mid = Math.floor((left + right) / 2);

if (arr[mid] === target) return mid; // 找到目标值，返回下标

else if (arr[mid] > target) right = mid - 1; // 在左半部分查找

else left = mid + 1; // 在右半部分查找

}

return -1; // 没有找到目标值，返回 -1

}

```

二分法查找的时间复杂度分析

在最坏的情况下，二分法查找需要比较的次数是 log₂n，其中 n 是数组的长度。假设数组长度为 8，那么最坏情况下，需要比较 3 次才能找到目标值。如果数组长度为 16，最坏情况下需要比较 4 次。由此可见，二分法查找的时间复杂度为 O(log n)。