Search for a range in a sorted array using C++

In this tutorial, we will learn how to search for a range of an element in the given sorted array in C++. Consider a given sorted array A with possibly duplicate elements. We have to find the starting and ending indices of a given target element B.

Also, Return {-1, -1} if element B is not found in the array
and Return the same indices twice if the element is present only once in the array.

This can be done using linear search (Time complexity: O(n)) but the efficient way to solve this problem is using binary search (Time complexity: O(log n)).

Example:

Example1:

INPUT,  A :  { 4, 5, 5, 6, 7, 7, 7, 10 }
TARGET, B = 7
OUTPUT:  4  6

Explanation:

The element B=7 is present in the array from indices 4 to 6.

Example2:

INPUT,  A :  { 1, 2, 2, 4, 4, 5 }
TARGET, B = 3
Output: -1 -1

Explanation:

The element B=3 is not present in the given array.

Search for a range using C++ Binary Search:

To find the initial and final index, We will have to call the binary search twice for the target value.

We will apply the first binary search by taking low as 0 and high as the last element of the array.

After completion of the first binary search if A[low] is equal to B, then low will be the initial index of the target value and set ans[0] = low. If A[low] is not equal to B, that means the target is not found in the array and We will return [-1, -1].

After getting the initial element as the result of the first binary search, We will move forward for the second binary search to get the final index value. For the second binary search, take low as the initial index value and high as the last element of the array.

After completion of the second binary search, high will be the final index of the target. Set ans[1] = high.

Return ans.

Implementation of the above algorithm in C++ is as follows:

#include<bits/stdc++.h>
using namespace std;
//Function to search the index range
vector<int> searchRange(vector<int> &A, int B) {
    vector<int> ans(2,-1);
    int low=0,high=A.size()-1,mid;
    //first binary search for initial index of B
    while(low<high){
        mid=(low+high)/2;
        if(A[mid]<B)
            low=mid+1;
        else
            high=mid;
    }
    if(A[low]!=B)
        return ans;
    else
        ans[0]=low;
    high=A.size()-1;
    //second binary search for final index of B
    while(low<high){
        mid=(low+high)/2 + 1;
        if(A[mid]>B)
            high=mid-1;
        else
            low=mid;
    }
    ans[1]=high;
    return ans;
}
int main(){
    vector<int> A={4,5,5,6,7,7,7,10};
    vector<int> ans;
    ans=searchRange(A,7);
    for(int i=0;i<2;i++){
        cout<<ans[i]<<" ";
    }
    return 0;
}

Output:

4 6

Also, refer

 

Leave a Reply

Your email address will not be published. Required fields are marked *