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.

garray012345678910125555555520

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]

C++

Java

Python

Ruby

#include <iostream>
#include <vector>
using namespace std;
int FindLowIndex(vector<int>& nums, int target) {
    return -2;
}
int FindHighIndex(vector<int>& nums, int target) {
    return -2;
}

#

#include <iostream> #include <vector> using namespace std; int FindLowIndex(vector<int>& nums, int target) { return -2; } int FindHighIndex(vector<int>& nums, int target) {

Enter to Rename, Shift+Enter to Preview

Test

Save

Reset

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:

Created with Fabric.js 3.6.6low012345678910125555555520midhighkey: 5Let's start with finding low index on array 'arr'We will move low and high towards each otheruntil low crosses high.

1 of 12

C++

Java

Python

Ruby

#include <iostream>
#include <vector>
using namespace std;
// Finding the low index of the target element
int FindLowIndex(vector<int>& nums, int target) {
    int low = 0;
    int high = nums.size() - 1;
    int mid = high / 2;
    while (low <= high) {
        int mid_elem = nums[mid];
        // Target value is less than the middle value
        if (mid_elem < target) {
            low = mid + 1;
        }
        // Target value is greater than or equal to the middle value
        else {
            high = mid - 1;
        }
        // Updating the mid value
        mid = low + (high - low) / 2;
    }
    if (low < nums.size() && nums[low] == target) {
        return low;
    }

#

#include <iostream> #include <vector> using namespace std; // Finding the low index of the target element int FindLowIndex(vector<int>& nums, int target) { int low = 0; int high = nums.size() - 1; int mid = high / 2;

Enter to Rename, Shift+Enter to Preview

Run

Save

Reset

Time complexity#

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

Space complexity#

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

Back

Rotate an Array by N Elements

Move All Zeros to the Beginning of the Array

Mark as Completed

Report an Issue

Prelude

Arrays

Linked Lists

Strings

Stacks and Queues

Trees

Graphs

Further Reading

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

Statement#