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
