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]
.
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, break
ing when we find
an instance of target
. If we never break
, then target
is not present,
so we can return the "error code" of [-1, -1]
early. Given that we did find
a valid left index, we can do a second linear scan, but this time from the
right. In this case, the first instance of target
encountered will be the
rightmost one (and because a leftmost one exists, there is guaranteed to also
be a rightmost one). We then simply return a list containing the two located
indices.
Complexity Analysis
Time complexity :
This brute-force approach examines each of the n
elements of nums
exactly twice, so the overall runtime is linear.
Space complexity :
The linear scan method allocates a fixed-size array and a few integers, so it has a constant-size memory footprint.
Intuition
Because the array is sorted, we can use binary search to locate the left and rightmost indices.
Algorithm
The overall algorithm works fairly similarly to the linear scan approach,
except for the subroutine used to find the left and rightmost indices
themselves. Here, we use a modified binary search to search a sorted array,
with a few minor adjustments. First, because we are locating the leftmost (or
rightmost) index containing target
(rather than returning true
iff we
find target
), the algorithm does not terminate as soon as we find a match.
Instead, we continue to search until lo == hi
and they contain some index
at which target
can be found.
The other change is the introduction of the left
parameter, which is a
boolean indicating what to do in the event that target == nums[mid]
; if
left
is true
, then we "recurse" on the left subarray on ties. Otherwise,
we go right. To see why this is correct, consider the situation where we find
target
at index i
. The leftmost target
cannot occur at any index
greater than i
, so we never need to consider the right subarray. The same
argument applies to the rightmost index.
The first animation below shows the process for finding the leftmost index, and the second shows the process for finding the index right of the rightmost index.
!?!../Documents/34_Search_for_a_Range_left.json:1280,720!?!
!?!../Documents/34_Search_for_a_Range_right.json:1280,720!?!
Complexity Analysis
Time complexity :
Because binary search cuts the search space roughly in half on each iteration, there can be at most iterations. Binary search is invoked twice, so the overall complexity is logarithmic.
Space complexity :
All work is done in place, so the overall memory usage is constant.
Analysis and solutions written by: @emptyset