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

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

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].

Thoughts

两次lower_bound，第二次用在target +1，无论找没找到最后都会落在target所在最后位置的后一个（如果有）前移一个就是target所在最后位置。

Code

/*
 * @lc app=leetcode id=34 lang=cpp
 *
 * [34] Find First and Last Position of Element in Sorted Array
 */

// @lc code=start
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if (nums.size() == 0) return vector<int>{-1, -1};
        const auto lower_bound = [&](int target) {
            int start = 0, end = nums.size() - 1;
            while (start < end) {
                int mid = start + (end - start) / 2;
                if (nums[mid] < target) start = mid + 1;
                else end = mid;
            }
            return start;
        };
        int l = lower_bound(target);
        if (nums[l] != target) return vector<int>{-1, -1};
        int h = lower_bound(target + 1);
        if (nums[h] == target) return vector<int>{l, h};
        return vector<int>{l, h - 1};
    }
};
// @lc code=end

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

        return start;
    }

    // find the first number that is greater than or equal to target.
    // could return A.length if target is greater than A[A.length-1].
    // actually this is the same as lower_bound in C++ STL.
    public int[] searchRange(int[] nums, int target) {
        int[] res = new int[]{-1, -1};
        int start = binSearch(nums, target);
        if (nums.length == start || nums[start] != target) {
            return res;
        }
        res[0] = start;
        res[1] = binSearch(nums, target + 1) - 1;
        return res;
    }
}

Analysis

复杂度O(lgn)