Find Low/High Index of a Key in a Sorted Array

Statement

We’re given a sorted array of integers, nums, and an integer value, target. Return the low and high index of the given target element. If the indexes are not found, return -1.

Note: The array can contain multiple duplicates with length in millions.

Example

In the array below, indices are shown in grey and values are shown in green. Note that the actual input can be very large in size.

According to the above example, the low and high indices for specific target values are listed below:

• For target= 1: low = 0 and high = 0
• For target= 2: low = 1 and high = 1
• For target= 5: low = 2 and high = 9

Sample input

nums = [1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 6, 6]
target = 5

Expected output

Low index: 15
High index: 17

Try it yourself