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$O(logn)$ runtime complexity.

Now that we have understood the problem, let’s check our knowledge by solving the MCQs given below:

Choose the correct option:

1

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?

A)

`[1, 3]`

B)

`[2, 4]`

C)

`[1, 4]`

D)

`[0, 2]`

Question 1 of 30 attempted

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")

Find First and Last Position of Element in Sorted Array

The time complexity of the provided algorithm is

The space complexity is

Copyright ©2024 Educative, Inc. All rights reserved

TRENDING TOPICS