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

Tags: Medium Binary Search

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

---

Given an array of integers nums 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].

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]

---

class Solution {
    int leftBoundSearch(vector<int> & nums, int target) {
        int n = nums.size();
        if (n == 0 || target <= nums[0]) return 0;
        if (target > nums.back()) return n;

        int left = 0, right = n - 1;
        while (left < right) {
            int middle = left + ((right - left) >> 1);
            if (nums[middle] < target) left = middle + 1;
            else right = middle;
        }
        return left;
    }
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int left = leftBoundSearch(nums, target);
        if (left == nums.size() || nums[left] != target) return {-1, -1};

        return {left, leftBoundSearch(nums, target + 1) - 1};
    }
};

其实我们也可以只使用一个二分查找的子函数，来同时查找出第一个和最后一个位置。如何只用查找第一个大于等于目标值的二分函数来查找整个范围呢，这里用到了一个小 trick，首先来查找起始位置的 target，就是在数组中查找第一个大于等于 target 的位置，当返回的位置越界，或者该位置上的值不等于 target 时，表示数组中没有 target，直接返回 {-1, -1} 即可。若查找到了 target 值，则再查找第一个大于等于 target+1 的位置，然后把返回的位置减1，就是 target 的最后一个位置，即便是返回的值越界了，减1后也不会越界，这样就实现了使用一个二分查找函数来解题