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!

Answer 2

I am not explaining I have given the code in java if you want you can improve it.

 public class Test {

public static int binSearch(int array[], int key, int left, int right,boolean lb)
{
int mid = left + (right-left)/2;
if (key < array[mid])
    return binSearch(array, key, left, mid-1,lb);
else if (key > array[mid])
    return binSearch(array, key, mid+1, right,lb);
else if (key == array[mid]){
    if(!lb){
    if(key==array[mid+1]){
        int ctr=mid+1;
        while(key==array[++ctr]);
        return ctr--;
      }
    else
        return mid;
    }
    else{
    if(key==array[mid-1]){
        int ctr=mid-1;
        while(key==array[--ctr]);
        return ctr++;
    }
    else
        return mid;
   }

}
return -0; // Not Found

}

public static void main(String[] args) {
int a[]={1,2,4,4,5,8,12,15,15,23,54};
int start=binSearch(a, 4, 0, a.length,true);
int end=binSearch(a, 15, 0, a.length,false);
System.out.println(end-start+1);// number are include
}

}

Answer 3

In Binary Search, you stop the recursive procedure when you find the required number or when the number is not in the list.
Here, you have to modify the Binary Search algorithm. Start with lower range, say a, keep repeating until you find a number less than a. While doing this maintain two indices say low and high. If the number you are comparing is less than a, update low else update high. Now you have the lower index, now recursively apply this procedure to find the number greater than this a. This index will give the starting index.
Now, do the complimentary for upper range, you'll get the ending index.
The answer is ending index - starting index + 1

imin = 0, imax = A.size()-1
low = 0, high = A.size()-1
while(imax >= imin)
{
   imid = mid(imin,imax)
   if(key < A[imid])
   {
       imax = imid -1
       high = imid
   }
   else if(key > A[imid])
   {
       imin = imid + 1
       low = imid
   }
   else 
   {
       high = imid
       break;
   }
 }

Now, once it comes out of the loop check if imin > imax, if yes then lower range index would be imax. Else, repeat the search again with imin = low and imax = high with the same key, till you reach the condition imin > imax. Repeat the same for the upper range.
The time complexity falls between O(log(n)) and O(n)

Answer 4

You need a modified binary search, one that has a parameter whether to find the first or last occurence of element.
You have to write yourself that modified binsearch.