JS数组搜索之折半搜索实现方法分析

什么是折半搜索

折半搜索，也称二分搜索，是一种高效的搜索算法，它可以在一个已经按照某种顺序排好序的数组中查找某个值的位置。折半搜索每次对数组进行“折半”，判断目标值在左半部分还是右半部分，然后重复这个过程，直到找到目标值或者确定目标值不存在于数组中。

如何实现折半搜索

在JavaScript中，可以通过以下代码实现一个折半搜索的函数：

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) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1; // target不存在于数组中
}

上述代码中的arr是要进行搜索的数组，target是要查找的值。函数会首先将搜索区间的左右边界left和right设为数组的第一个和最后一个位置，然后在循环内部进行折半搜索。循环条件为left <= right，因为如果target不存在于数组中，最终的搜索区间会变成left > right，循环将退出。每次循环中，使用Math.floor((left + right) / 2)计算中间位置mid，然后根据arr[mid]与target的大小关系更新搜索区间的左右边界left和right。如果arr[mid]等于target，直接返回mid，表示找到了目标值的位置。如果循环结束后仍然没有找到目标值，返回-1表示目标值不存在于数组中。

折半搜索的时间复杂度

假设待搜索的数组长度为N，折半搜索每次将搜索区间缩小一半，因此最多需要进行log2(N)次比较才能找到目标值或确定目标值不存在于数组中。因此，折半搜索的时间复杂度为O(log2(N))，相比于线性搜索的O(N)时间复杂度，折半搜索具有更高的效率。

示例说明

示例1

我们有一个已经排好序的数组arr，包含如下元素：

const arr = [1, 3, 4, 5, 7, 8, 10];

现在我们要查找数字5的位置，可以调用上述实现折半搜索的函数：

const index = binarySearch(arr, 5);
console.log(index); // 3

代码会返回数字5在数组中的位置，应该是3。

示例2

现在我们有一个乱序的数组arr2，包含如下元素：

const arr2 = [8, 3, 5, 1, 10, 7, 4];

我们可以先对数组进行排序，然后再进行折半搜索。在这里，我们使用JavaScript原生的sort函数对数组进行排序：

const sortedArr2 = arr2.sort((a, b) => a - b);
const index = binarySearch(sortedArr2, 5);
console.log(index); // 2

排序后的sortedArr2是排好序的数组，然后我们调用折半搜索函数查找数字5的位置。代码会返回2，因为在排好序的数组中，数字5的位置是2。