[LeetCode] 34. 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]

Constraints:
0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums is a non-decreasing array.
-109 <= target <= 109

在有序数组中查找元素的第一个和最后一个位置。

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

进阶：

你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

这道题的最优解是二分法。思路是通过二分法分别找到第一个插入的位置和第二个插入的位置。注意找第一个位置和第二个位置的不同，两者都是正常的二分法，但是找第一个位置的时候要先顾到 start pointer，同时要优先动 start 指针；找第二个位置的时候要先顾到 end pointer，也优先动 end 指针。这道题很考察对二分法模板的运用。

复杂度

时间O(logn)
空间O(1)

代码

Java实现

class Solution {
    public int[] searchRange(int[] nums, int target) {
        // corner case
        if (nums == null || nums.length == 0) {
            return new int[] { -1, -1 };
        }

        // normal case
        int start = findFirst(nums, target);
        if (start == -1) {
            return new int[] { -1, -1 };
        }
        int end = findLast(nums, target);
        return new int[] { start, end };
    }

    private int findFirst(int[] nums, int target) {
        int start = 0;
        int end = nums.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] < target) {
                start = mid;
            } else {
                end = mid;
            }
        }
        if (nums[start] == target) {
            return start;
        }
        if (nums[end] == target) {
            return end;
        }
        return -1;
    }

    private int findLast(int[] nums, int target) {
        int start = 0;
        int end = nums.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] > target) {
                end = mid;
            } else {
                start = mid;
            }
        }
        if (nums[end] == target) {
            return end;
        }
        if (nums[start] == target) {
            return start;
        }
        return -1;
    }
}

JavaScript实现

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function(nums, target) {
    // corner case
    if (nums === null || nums.length === 0) {
        return [-1, -1];
    }
    // normal case
    let start = findFirst(nums, target);
    if (start === -1) {
        return [-1, -1];
    }
    let end = findLast(nums, target);
    return [start, end];
};

var findFirst = function(nums, target) {
    let start = 0;
    let end = nums.length - 1;
    while (start + 1 < end) {
        let mid = Math.floor(start + (end - start) / 2);
        if (nums[mid] < target) {
            start = mid;
        } else {
            end = mid;
        }
    }
    if (nums[start] === target) return start;
    if (nums[end] === target) return end;
    return -1;
};

var findLast = function(nums, target) {
    let start = 0;
    let end = nums.length - 1;
    while (start + 1 < end) {
        let mid = Math.floor(start + (end - start) / 2);
        if (nums[mid] > target) {
            end = mid;
        } else {
            start = mid;
        }
    }
    if (nums[end] === target) return end;
    if (nums[start] === target) return start;
    return -1;
};

相关题目

34. Find First and Last Position of Element in Sorted Array
658. Find K Closest Elements