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

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

Question

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.

思路

这题的思路比较直球，就是用二分查找的左边界法和右边界法去搜索。

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function(nums, target) {
    const leftBound = () => {
        let left = 0;
        let right = nums.length;
        while (left < right) {
            const mid = ~~((left + right) / 2);
            const v = nums[mid];
            if (v === target) {
                right = mid;
            } else if (v > target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    };
    const rightBound = () => {
        let left = 0;
        let right = nums.length;
        while (left < right) {
            const mid = ~~((left + right) / 2);
            const v = nums[mid];
            if (v === target) {
                left = mid + 1;
            } else if (v > target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left - 1;
    };
    const left = leftBound();
    const right = rightBound();
    if (left > -1 && left <= right && right < nums.length && nums[left] === nums[right]) {
        return [left, right];
    }
    return [-1, -1];
};

End

对于二分查找的三个形式：

• 基础查找
• 左边界查找
• 右边界查找

要比较熟悉，特别是细节的+1, -1, <=, <的差别。