## 34. Search for a Range

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

b'
\n\n

#### Approach #1 Linear Scan [Accepted]

\n

Intuition

\n

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

\n

Algorithm

\n

First, we do a linear scan of `nums` from the left, `break`ing 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.

\n\n

Complexity Analysis

\n
\n
• \n

Time complexity : \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 : \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
\n
\n

#### Approach #2 Binary Search [Accepted]

\n

Intuition

\n

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

\n

Algorithm

\n

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.

\n

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\n`left` 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\n`target` 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.

\n

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.

\n

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

\n

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

\n\n

Complexity Analysis

\n
\n
• \n

Time complexity : \n

\n

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

\n
• \n
• \n

Space complexity : \n

\n

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

\n
• \n
\n
\n

Analysis and solutions written by: @emptyset

\n
'