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