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#

To test our code, the input array will be:

[1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 6, 6, 9]

Solution#

Linearly scanning the sorted array for low and high indices is highly inefficient since our array size can be in the millions. Instead, we will use a slightly modified binary search to find the low and high indices of a given target.

We need to binary search twice: the first time to find the low index and a second time to find the high index.

Low index#

Let’s look at the algorithm for finding the low index:

• At every step, consider the array between low and high indices and calculate the mid index.
• If the element at the mid index is less than the target, the value of low becomes mid + 1 (to move towards the start of range). The value of high remains the same.
• If the element at mid is greater or equal to the target, the value of high becomes mid - 1. The value of low remains the same.
• When the value of low is greater than high, low would point to the first occurrence of the target.
• If the element at low does not match the target, return -1. It means that the target doesn’t exist in the array.

High index#

Similarly, we can find the high index by slightly modifying the above algorithm:

• If the value at the mid index is less than or equal to the target, the value of low becomes mid + 1.
• If the value at mid is greater than the target, the value of high becomes mid - 1.

Let’s find low and high indices of $5$ in the given example below:

Time complexity#

Since we are using binary search, the time complexity is logarithmic, $O(logn)$. Even though we do the binary search twice, the asymptotic time complexity is still $O(logn)$.

Space complexity#

The space complexity is constant, $O(1)$, since no extra storage is used.