Approach #1 Linear Scan [Accepted]

Intuition

Checking every index for target exhausts the search space, so it must work.

Algorithm

First, we do a linear scan of nums from the left, breaking when we find\nan instance of target. If we never break, then target is not present,\nso we can return the "error code" of [-1, -1] early. Given that we did find\na valid left index, we can do a second linear scan, but this time from the\nright. In this case, the first instance of target encountered will be the\nrightmost one (and because a leftmost one exists, there is guaranteed to also\nbe a rightmost one). We then simply return a list containing the two located\nindices.

Complexity Analysis

\n
• \n

  Time complexity : $$O(n)$$ \n

  \n

  This brute-force approach examines each of the n elements of nums\nexactly twice, so the overall runtime is linear.

  \n
\n
• \n

  Space complexity : $$O(1)$$ \n

  \n

  The linear scan method allocates a fixed-size array and a few integers,\nso it has a constant-size memory footprint.

  \n
\n

Approach #2 Binary Search [Accepted]

Intuition

Because the array is sorted, we can use binary search to locate the left\nand rightmost indices.

Algorithm

The overall algorithm works fairly similarly to the linear scan approach,\nexcept for the subroutine used to find the left and rightmost indices\nthemselves. Here, we use a modified binary search to search a sorted array,\nwith a few minor adjustments. First, because we are locating the leftmost (or\nrightmost) index containing target (rather than returning true iff we\nfind target), the algorithm does not terminate as soon as we find a match.\nInstead, we continue to search until lo == hi and they contain some index\nat which target can be found.

The other change is the introduction of the left parameter, which is a\nboolean indicating what to do in the event that target == nums[mid]; if\nleft is true, then we "recurse" on the left subarray on ties. Otherwise,\nwe go right. To see why this is correct, consider the situation where we find\ntarget at index i. The leftmost target cannot occur at any index\ngreater than i, so we never need to consider the right subarray. The same\nargument applies to the rightmost index.

The first animation below shows the process for finding the leftmost index,\nand the second shows the process for finding the index right of the rightmost\nindex.

!?!../Documents/34_Search_for_a_Range_left.json:1280,720!?!

!?!../Documents/34_Search_for_a_Range_right.json:1280,720!?!

Complexity Analysis

\n
• \n

  Time complexity : $$O(lgn)$$ \n

  \n

  Because binary search cuts the search space roughly in half on each\niteration, there can be at most $$\\lceil lgn \\rceil$$ iterations. Binary\nsearch is invoked twice, so the overall complexity is logarithmic.

  \n
\n
• \n

  Space complexity : $$O(1)$$ \n

  \n

  All work is done in place, so the overall memory usage is constant.

  \n
\n

Analysis and solutions written by: @emptyset