Efficient algo to find number of integers in a sorted array that are within a certain range in O(log(N)) time?

Bhaskar Published at Dev

Bhaskar

I came across a interview question that has to be done in O(logn)

Given a sorted integer array and a number, find the start and end indexes of the number in the array.

Ex1: Array = {0,0,2,3,3,3,3,4,7,7,9} and Number = 3 --> Output = {3,6} 

Ex2: Array = {0,0,2,3,3,3,3,4,7,7,9} and Number = 5 --> Output = {-1,-1}

I am trying to find an efficient algo for this but so fat have not been successful.

Ron Teller

You can use the concept of binary search to find the starting and ending index:

To find the starting index, you halve the array, if the value is equal to or greater than the input number, repeat with the lower half of the array, otherwise repeat with the higher half. stop when you reached an array of size 1.
To find the starting index, you halve the array, if the value is greater than the input number, repeat with the lower half of the array, otherwise repeat with the higher half. stop when you reached an array of size 1.

Note that when we reached an array of size 1, we may be one cell next to the input number, so we check if it equals the input number, if not, we fix the index by adding/decreasing 1 from the index we found.

findStartIndex(int[] A, int num)
{
    int start = 0; end = A.length-1;

    while (end != start) 
    {
        mid = (end - start)/2;

        if (A[mid] >= num)
            end = mid;
        else
            start = mid;
    }

    if(A[start] == num) 
        return start;
    else 
        return start+1;
}

findEndIndex(int[] A, int num)
{
    int start = 0; end = A.length-1;

    while (end != start) 
    {
        mid = (end - start)/2;

        if (A[mid] > num)
            end = mid;
        else
            start = mid;
    }

    if(A[start] == num) 
        return start;
    else 
        return start-1;
}

And the whole procedure:

int start = findStartIndex(A, num);

if (A[start]!=num) 
{ 
     print("-1,-1"); 
}
else
{
     int end = findEndIndex(A, num);
     print(start, end);
}

Collected from the Internet

Please contact [email protected] to delete if infringement.