34. Find First and Last Position of Element in Sorted Array

Leetcode

https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

題目

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

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

You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

Example 3:

Input: nums = [], target = 0
Output: [-1,-1]

解答

• 方法一

var searchRange = function(nums, target) {
    let startIndex = -1;
    let endIndex = -1;
    
    const searchLeft = (start, end) => {
        while(start < end) {
            const mid = Math.floor((start+end) / 2);
            if(target === nums[mid]) {
                end = mid;
            } else {
                start = mid + 1;
            }
        }
        return start;
    }
    const searchRight = (start, end) => {
        while(start < end) {
            const mid = Math.ceil((start+end) / 2);
            if(target === nums[mid]) {
                start = mid;
            } else {
                end = mid - 1;
            }
        }
        return start;
    }
    
    let start = 0;
    let end = nums.length - 1;
    
    while(start <= end) {
        const mid = Math.floor((start+end) / 2);
        if(target === nums[mid]) {
            // 找到 target 後，往左找出 index 最小的 target
            startIndex = searchLeft(start, mid);
            // 找到 target 後，往右找出 index 最大的 target
            endIndex = searchRight(mid, end);
            return [startIndex, endIndex];
        } else if (target > nums[mid]) {
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }
    return [startIndex, endIndex];
};

Runtime: 103 ms, faster than 15.89% of JavaScript online submissions for Find First and Last Position of Element in Sorted Array.

Memory Usage: 39.9 MB, less than 91.37% of JavaScript online submissions for Find First and Last Position of Element in Sorted Array.

測資

let nums = [5,7,7,8,8,10], target = 8; // [3, 4]
// nums = [5,7,7,8,8,10], target = 6; // [-1,-1]
// nums = [], target = 0; // [-1,-1]

console.log(searchRange(nums, target));