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

Question

I have a sorted array of integers:

{1,2,4,4,5,8,12,15,15,23,54}

I want to find how many numbers in that array fall between a range, say 4 and 15.

{4,4,5,6,12,15,15}

So, there are 7 items in the array that are within that range.

I need to do this in O(log(N)) time, and I thought I could use a binary search, but that wouldn't find the lower and upper bounds because of the duplicates.

How can this be done in O(log(N)) time?

I've thought of looping from the front, and then from the end, but that could be up to O(N)

Answer 1

It can be done in O(logN) time by range binary search for the lower bound and upper bound. Range binary search for the lower bound and the upper bound are different. Here different means they have different stopping criteria and return step.

1. For the lower bound (left range), you can call the following function to get the index in the sorted array where the value is larger or equal than it, -1 otherwise.

   int binarySearchForLeftRange(int a[], int length, int left_range)
   {
       if (a[length-1] < left_range)
           return -1;
   
       int low = 0;
       int high = length-1;
   
       while (low<=high)
       {
           int mid = low+((high-low)/2);
   
           if(a[mid] >= left_range)
               high = mid-1;
           else //if(a[mid]<i)
               low = mid+1;
       }
   
       return high+1;
   }
   

2. For the upper bound (right range), you can call the following function to get the index in the sorted array where the value is smaller or equal than it, -1 otherwise.

   int binarySearchForRightRange(int a[], int length, int right_range)
   {
       if (a[0] > right_range)
           return -1;
   
       int low = 0;
       int high = length-1;
   
       while (low<=high)
       {
           int mid = low+((high-low)/2);
   
           if(a[mid] > right_range)
               high = mid-1;
           else //if(a[mid]<i)
               low = mid+1;
       }
   
       return low-1;
   }
   

3. Finally, if you want to get the number of how many elements within this range, it's easy based on return values of these two above functions.

   int index_left = binarySearchForLeftRange(a, length, left_range);
   int index_right = binarySearchForRightRange(a, length, right_range);
   
   if (index_left==-1 || index_right==-1 || index_left>index_right)
       count = 0;
   else
       count = index_right-index_left+1;
   

---

Test: (with duplicates)

    int a[] = {1,2,4,4,5,8,12,15,15,23,54};
    int length = sizeof(arr)/sizeof(arr[0]);

    int left_range = 4;
    int right_range = 15;
    int index_left = binarySearchForLeftRange(a, length, left_range); // will be 2
    int index_right = binarySearchForRightRange(a, length, right_range); // will be 8

    int count; // will be 7
    if (index_left==-1 || index_right==-1 || index_left>index_right)
        count = 0;
    else
        count = index_right-index_left+1;

---

EDIT: Of course, you can merge the first two functions into one by passing one extra flag to indicate it as lower bound or upper bound, though it will be much more clear if not. Your choice!