ProDeveloperTutorial.com

Tutorials and Programming Solutions
Menu
  • Shell Scripting
  • System Design
  • Linux System Programming
  • 4g LTE
  • Coding questions
  • C
  • C++
  • DSA
  • GIT

Given a sorted array, find the starting and ending index that matches the target – 2 solutions using C++

prodevelopertutorial February 12, 2019

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

 

 

 

List Of Tutorials available in this website:

C Programming 20+ ChaptersC++ Programming 80+ Chapters
100+ Solved Coding QuestionsData Structures and Algorithms 85+ Chapters
System design 20+ ChaptersShell Scripting 12 Chapters
4g LTE 60+ ChaptersMost Frequently asked Coding questions
5G NR 50+ ChaptersLinux System Programming 20+ chapters
Share
Email
Tweet
Linkedin
Reddit
Stumble
Pinterest
Prev Article
Next Article

About The Author

prodevelopertutorial

Daily we discuss about competitive programming questions, join us at:   Telegram Channel

ProDeveloperTutorial.com

Tutorials and Programming Solutions
Copyright © 2021 ProDeveloperTutorial.com
Get top courses from: Educative.io