当前位置：网站首页>js查找数组下标

js查找数组下标

2022-04-22 00:33:00 【马德里甜欣】

题目：

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

方法1:递归
思路：先找到中间位置，判断是否是需要寻找的目标值，如果是就返回，不是的话判断目标值和中间元素的大小，然后继续向左右子树递归寻找
复杂度：时间复杂度O(logn)，空间复杂度O(logn)，递归栈大小

方法2:非递归
思路：定义left、right指针，比较目标元素和中间元素的大小，然后不断缩小左右指针的范围继续寻找目标元素
复杂度：时间复杂度O(logn)，空间复杂度O(1)

此处使用方法二

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function (nums, target) {
    var left = 0, right = nums.length - 1
    while (left <= right) {
        var mid = (left + right) >> 1;
        if (nums[mid] > target) {
            right = mid - 1
        }
        if (nums[mid] === target) return mid;
        if (nums[mid] < target) {
            left = mid + 1
        }
    }
    return -1
};