二分查找基本实现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 代码：

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, left, mid - 1); // 目标元素在左侧，继续在左侧部分查找
  } else {
    return binarySearch(arr, target, mid + 1, right); // 目标元素在右侧，继续在右侧部分查找
  }
}

// 示例用法
const nums = [1, 3, 5, 7, 9];
const target = 5;
const result = binarySearch(nums, target);
console.log(result); // 输出: 2

以上代码定义了一个 `binarySearch` 函数，它接受一个有序数组 `arr`、要查找的目标元素 `target`，以及可选的左右边界参数 `left` 和 `right`。函数内部使用递归来不断将搜索范围缩小，直到找到目标元素或者无法继续缩小范围（即找不到目标元素）。如果找到目标元素，返回其索引；否则，返回 -1 表示找不到。在示例用法中，我们使用给定的有序数组和目标元素调用函数，并输出结果。