二分查找基本实现js

二分查找的基本实现（binary search）在JavaScript中是通过递归或循环来完成的。下面是一个简单的递归实现示例[^1]：

function binarySearch(arr, target, left = 0, right = arr.length - 1) {
    if (left > right) {
        return -1; // 如果目标不在数组内，返回-1表示未找到
    }
    
    let 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); // 目标小于中间元素，搜索左半部分
    }
}

// 示例使用
let sortedArray = [1, 3, 5, 7, 9];
console.log(binarySearch(sortedArray, 7)); // 输出：3

二分查找前提是数组必须是有序的，如果输入的是无序数组，它将无法正确工作[^2]。

相关问题

二分查找基本实现js 原理

二分查找的基本实现原理是基于JavaScript的有序数组。其工作流程如下[^1]:
1. **初始化**：确定数组的起始索引（low）和结束索引（high），通常初始时low为0，high为数组长度减一。
2. **比较**：计算中间索引（mid）= (low + high) / 2，然后比较中间元素的值与目标值。
3. **判断**：如果中间元素等于目标值，查找完成；如果目标值小于中间元素，则在数组左半部分继续查找（更新high为mid - 1）；反之，在右半部分查找（更新low为mid + 1）。
4. **递归**：重复以上步骤直到找到目标值或low大于high。

以下是一个简单的JavaScript二分查找实现示例[^2]：

function binarySearch(arr, target) {
    let low = 0;
    let high = arr.length - 1;

    while (low <= high) {
        let mid = Math.floor((low + high) / 2);
        if (arr[mid] === target) {
            return mid; // 找到目标值
        } else if (arr[mid] < target) {
            low = mid + 1; // 目标值大于当前元素，向右半部分查找
        } else {
            high = mid - 1; // 目标值小于当前元素，向左半部分查找
        }
    }

    return -1; // 没找到目标值，返回-1表示不存在
}

// 示例
let sortedArray = [1, 3, 5, 7, 9];
console.log(binarySearch(sortedArray, 7)); // 输出：3

二分查找js 实现步骤

在JavaScript中，二分查找（Binary Search）的实现步骤如下：

1. **前提条件**：确保输入的数组是已排序的（升序或降序）。这是二分查找的基础，因为算法依赖于中间元素来缩小搜索范围。

2. **初始化**：定义两个指针，`left`表示数组的开始索引（通常是0），`right`表示数组的结束索引（通常是数组长度减1）。

3. **循环条件**：当`left`小于等于`right`时，循环继续。这表示搜索范围尚未空。

4. **计算中间位置**：取`left`和`right`的平均值，得到中间索引`mid`，`mid = Math.floor((left + right) / 2)`。

5. **比较中间元素**：如果中间元素恰好是我们正在寻找的值，那么返回该索引。如果中间元素大于目标值，则在数组的左半部分（从`left+1`到`mid`）重复步骤；如果中间元素小于目标值，则在右半部分（从`mid+1`到`right`）重复步骤。

6. **更新指针**：根据比较结果，调整`left`或`right`，直到找到目标值或搜索范围为空。

7. **没有找到**：如果循环结束后仍然没有找到目标值，说明目标值不在数组中，此时可以返回`-1`作为标记。

以下是一个简单的二分查找的JavaScript实现示例[^1]：

function binarySearch(array, target) {
    let left = 0;
    let right = array.length - 1;

    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (array[mid] === target) {
            return mid;
        } else if (array[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1; // 如果找不到目标值，返回-1
}

// 示例
let sortedArray = [1, 3, 5, 7, 9];
console.log(binarySearch(sortedArray, 5)); // 输出：2