Find Low/High Index of a Key in a Sorted Array
Understand how to find the low and high index of a target value in a sorted array with duplicates by applying a modified binary search method twice. Learn to perform this search efficiently with logarithmic time complexity and constant space.
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 andhigh= 0 - For
target= 2:low= 1 andhigh= 1 - For
target= 5:low= 2 andhigh= 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
To test our code, ...