34. Search for a Range

Tags

1. Array
2. Binary Search

Given an array of integers sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example, Given [5, 7, 7, 8, 8, 10] and target value 8, return [3, 4].

题意：

给你一个升序排列的整数数组，找到指定数字的起始和结尾位置，你的算法运行时间必须为O(log n)。如果目标值没有在数组中找到就返回[-1,-1].

分析：

参考33题

思路：

二分查找，进行两次分别找到起始和结尾

复杂度：

时间复杂度O(log(n));

Js实现：

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function(nums, target) {
    const start = targetPos(target,nums, false);
    const end = targetPos(target, nums, true);
    return [start, end];
};

function targetPos(target, nums, isLast) {
    let lo = 0; 
    let hi = nums.length - 1;
    let pos = -1;
    while(lo <= hi) {
        let mid = Math.floor((hi+lo)/2);

        if(nums[mid] == target) pos = mid;

        if(isLast) {
            if(nums[mid] <= target) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        } else {
            if(nums[mid] < target) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
    }
    return pos;
}