In many real-world scenarios, efficiently finding the starting and ending positions of a target value in a sorted array is essential. For instance, in systems monitoring, log files record events with timestamps, etc. To investigate issues, it's often necessary to locate the range of log entries for a specific event type. Similar problems arise in other contexts as well, such as searching library databases for books published in a specific year, analyzing customer transaction records for a particular date, identifying specific sensor readings in IoT systems, and querying movie databases for films released in a given year. In all these cases, quick and accurate access to specific data ranges is important.
Given an array of integers nums
sorted in non-decreasing order and an integer target
, find the starting and ending position of the given target
value within the array.
If target
is not found in the array, return [-1, -1]
.
0 <= nums.length <= 10
5
-10
9
<= nums[i] <= 10
9
nums
is a non-decreasing array.
-10
9
<= target <= 10
9
Note: Our algorithm will take
runtime complexity.
Now that we have understood the problem, let’s check our knowledge by solving the MCQs given below:
Choose the correct option:
Given the sorted array nums = [1, 2, 2, 2, 3, 4, 5]
and target = 2
, what will be the output of the function that finds the starting and ending position of the target value?
[1, 3]
[2, 4]
[1, 4]
[0, 2]
To write an algorithm with
Algorithm steps
Define the findBound
function:
Takes three arguments: the array nums
, the target value target
, and a boolean isFirst
to indicate whether to find the first or last occurrence of the target.
Initialize variables:
Set begin
to 0.
Set end
to the last index of the array.
Iterate until begin
is greater than end
:
Calculate the middle index mid
as (begin + end) // 2
.
Use the value of the middle element to decide the next steps.
Handle cases cased on comparison with target
:
If nums[mid] == target
:
For first occurrence (isFirst
is true
):
If mid == begin
or nums[mid - 1] != target
, return mid
.
Otherwise, update end = mid - 1
.
For last occurrence (isFirst
is false
):
If mid == end
or nums[mid + 1] != target
, return mid
.
Otherwise, update begin = mid + 1
.
If nums[mid] > target
:
Update end = mid - 1
.
If nums[mid] < target
:
Update begin = mid + 1
.
Return -1 If target not found:
At the end of the findBound
function, return -1 if the target was not found.
Implement the searchRange
function:
Call findBound
with isFirst
set to true
to find the first occurrence.
If the result is -1, return [-1, -1]
since the target is not in the array.
Otherwise, call findBound
with isFirst
set to false
to find the last occurrence.
Return the result as [first_occurrence, last_occurrence]
.
This algorithm ensures that we efficiently locate the boundaries of the target value in a sorted array with a logarithmic runtime, making it suitable for large datasets.
The following illustration shows the algorithm explained above:
Code
Let’s have a look at the code for the algorithm we just discussed.
def find_bound(nums, target, isFirst):# Initialize the beginning and end indicesbegin, end = 0, len(nums) - 1# Perform binary searchwhile begin <= end:# Calculate the middle indexmid = (begin + end) // 2# Check if the middle element is the targetif nums[mid] == target:if isFirst:# Check if it is the first occurrenceif mid == begin or nums[mid - 1] != target:return midelse:end = mid - 1else:# Check if it is the last occurrenceif mid == end or nums[mid + 1] != target:return midelse:begin = mid + 1elif nums[mid] > target:# Adjust end index for left subarrayend = mid - 1else:# Adjust begin index for right subarraybegin = mid + 1return -1def search_range(nums, target):# Find the first occurrence of targetfirst = find_bound(nums, target, True)# If the target is not found, return [-1, -1]if first == -1:return [-1, -1]# Find the last occurrence of targetlast = find_bound(nums, target, False)return [first, last]# Driver code with examplesexamples = [([5, 7, 7, 8, 8, 10], 8),([5, 7, 7, 8, 8, 10], 6),([2, 2, 2, 2, 2], 2),([1, 3, 5, 7], 7),([1, 3, 5, 7], 4)]for nums, target in examples:result = search_range(nums, target)print(f"Array: {nums}, Target: {target}, Result: {result}\n")
The time complexity of the provided algorithm is
The space complexity is