Arrays: Given a sorted array, find the starting and ending index that matches the target

Given a sorted array and an element “k”. Get the start index and the end index of the given “k” value.

Example 1:

Array: [1, 2, 3, 4, 4, 4, 5, 6]
K = 4
Output: [3, 5]

Example 2:

Array: [1, 3, 3, 4, 5, 6, 6, 6]
K = 10
Output: [-1, -1]

We can solve this problem by 2 methods.

Method 1: 

By using library function “lower_bound” and “upper_bound”.

lower_bound will give the lower index of the value that matches to the key provided.

upper_bound will give the upper index of the value of the key matched.

Hence by using both of the methods, we get the result.

Method 2: 

By using binary search method.

Here we use binary search 2 times.
One to get the starting index and another is ending index.

Solution in C++

#include<iostream>
#include<string>
#include<set>
#include<vector>

using namespace std;

// by using STL methods
vector<int> get_range_method_1(vector<int> &array, int target)
{
    int lower_index = lower_bound(array.begin(), array.end(), target)-array.begin();

    // if the number is not present in the array, then send error
    if(array[lower_index] != target) 
        return vector<int>{-1, -1};

    int upper_index = upper_bound(array.begin(), array.end(), target)-array.begin();
        return vector<int>{lower_index, upper_index-1};
}


int binary_search_for_lower_index(vector<int>& array, int target) 
{
    int left = -1;
    int right = array.size();

    while (right - left > 1) 
    {
        int mid = (left + right) / 2;
        if (array[mid] >= target) 
            right = mid;
        else                     
            left = mid;
    }
    return right;
}

int binary_search_for_upper_index(vector<int>& array, int target) 
{
    int left = -1;
    int right = array.size();

    while (right - left > 1) 
    {
        int mid = (left + right) / 2;
        if (array[mid] > target) 
            right = mid;
        else                    
            left = mid;
    }
    return right;
}

// by using binary search 2 times.
vector<int> get_range_method_2(vector<int> &array, int target)
{
    int lower_index = binary_search_for_lower_index(array, target);
    int upper_index = binary_search_for_upper_index(array, target);
    
    vector<int> result(2, -1);
    if (lower_index < upper_index) 
    {
        result[0] = lower_index;
        result[1] = upper_index - 1;
    }
    return result;
}



int main()
{
    vector<int> array = {1, 2, 3, 4, 4, 4, 4, 5, 6};

    //test case 1
    int target = 4;
    
    //test case 2
    //int target = 7;
    
    cout<<"The given array is "<<endl;
    for (int i = 0; i < array.size(); i++)
    {
        cout <<array[i] << " ";
    }
    cout<<endl<<"The target is = "<<target<<endl;

    vector<int> result = get_range_method_1(array, target);

    cout<<"\n\nThe solution by using method 1 is "<<endl;
    for (int i = 0; i < result.size(); i++)
    {
        cout <<result[i] << " ";
    }
    cout<<endl;


    vector<int> result_1 = get_range_method_2(array, target);

    cout<<"\n\nThe solution by using method 2 is "<<endl;
    for (int i = 0; i < result_1.size(); i++)
    {
        cout <<result_1[i] << " ";
    }
    cout<<endl;

    return 0;
}

Output:

The given array is
1 2 3 4 4 4 4 5 6
The target is = 4


The solution by using method 1 is
3 6


The solution by using method 2 is
3 6