Challenge Description
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:

Example 2:

Naive Solution
Linear scan array from left to right or from right to left.
Find the first index with given value. A trivial optimization here is when we find current element is greater than target(search left to right), we won’t search the left elements.
Time complexity: $O(N)$

Binary search
Naive approach will not meet the challenge requirement. We can use the approach of binary search, but it’s a variant of original binarysearch.
Take search first left position for example, When we got an index(suppose idx) where value equal target, we store the current position and safely ignore the right part [idx ~ ..]
of the array, so we update the hi
pivot.
Search last right position is similar.
Time complexity: $O(logN)$.

Join my Email List for more helpful insights, It's Free!😋