JS实现一个函数,用于查找一个数字在一个有序数组中的位置(不存在则返回-1),要求使用二分查找法

好的，很高兴能够为您服务。下面是实现代码：

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;
}

这个函数实现了二分查找法，使用了 while 循环。首先，我们确定左边界 left 和右边界 right，分别为 0 和数组长度减 1。然后每次取中间位置，如果中间位置的元素等于目标元素，那么直接返回该位置。如果中间位置的元素小于目标元素，则说明目标元素在右半部分，将左边界 left 移动到 mid + 1 处。如果中间位置的元素大于目标元素，则说明目标元素在左半部分，将右边界 right 移动到 mid - 1 处。最后，如果 while 循环结束时都没有找到目标元素，说明不存在该元素，返回 -1。

希望这个实现能够帮到您。

相关问题

在有序数组中查找某个数字首次出现的位置的库函数

在计算机科学中，特别是在编程语言中，寻找有序数组中特定数字首次出现位置的常用算法通常是二分查找法（Binary Search）。这种方法基于数组已经排序的前提，通过比较目标值与中间元素，逐步缩小搜索范围，直到找到目标或确定目标不存在于数组中。

对于查找的操作，许多编程库都会提供现成的函数来实现这个功能。例如，在Python中可以使用内置的`bisect_left()`函数（如果数组已排序），而在C++标准库中，你可以使用`std::lower_bound()`函数。在JavaScript中，虽然没有直接的库函数，但也可以自定义类似的功能。

如果你想要编写这样的函数，伪代码大概会像这样：

# Python 示例
import bisect

def find_first_occurrence(arr, target):
    if arr is None or len(arr) == 0:
        return -1  # 如果数组为空或无效，返回-1表示未找到
    index = bisect.bisect_left(arr, target)
    if index < len(arr) and arr[index] == target:
        return index  # 找到等于目标的第一个索引
    else:
        return index  # 目标不存在，返回第一个大于或等于target的位置

在数组中查找元素key，返回查找到的下标，如没有找到返回-1

在数组中查找特定元素（key）并返回其索引的过程通常被称为线性搜索，因为它是从数组的第一个元素开始逐个比较，直到找到匹配项或遍历完整个数组。如果找到对应的元素，则返回该元素的索引；如果没有找到，由于数组的有序性或无序性不同，处理方式也不同：

1. **有序数组**（如升序排序的数组）：二分查找效率较高。从中间元素开始，如果 key 小于中间元素，则在左半部分继续查找，反之则在右半部分。这个过程会不断缩小查找范围，直到找到 key 或确定不存在。

2. **无序数组**（未排序或随机排列）：只能简单地从第一个元素逐个比对，直到找到或搜索完所有元素。这通常时间复杂度为 O(n)，其中 n 为数组长度。

如果需要在 JavaScript 中实现这样的功能，可以编写如下的函数：

function searchArray(array, key) {
    for (let i = 0; i < array.length; i++) {
        if (array[i] === key) {
            return i;
        }
    }
    return -1;
}