Finding range in O(log n) in sorted array

So, the question is to find the range of the number in a sorted array.

Eg: in a list [1,2,3,4,4,4,4,4,4,5] , the range of 4 is 3 to 9.

To get O(log n) we’ll use Binary search. We’ll actually use it twice to find upper and lower range.

To get the lower range, we would want to slide to the “Left” of the array overtime (Since its sorted). A slight modification in Binary search would give us the left most value:

while lower_bound < upper_bound:
        mid = (upper_bound+lower_bound)/2
        if B <= A[mid]:
            upper_bound = mid
        else:
            lower_bound= mid+1

(upper_bound + lower_bound)/2 would give us floor value of the integer.

So, for every iteration, if A[mid] is <= the target number, the starting range of the number is either at A[mid] or is at left of it. So, we set the upper bound at mid (not mid-1, as the current element could itself be the upper limit).

If the number is greater then the mid, the lowerbound should be mid+1 , this should be no-brainer.

Next we need to find the upper bound, so we need to slide right of the array.

mid = (upper_bound+lower_bound)/2+1

Also, we won’t change the value stored at lower_bound. Since the upper_bound will be at lower_bound index or at the right of it.

    while  lower_bound < upper_bound:
        mid = (lower_bound+upper_bound)/2+1
        if B < A[mid]:
            upper_bound = mid-1
        else:
            lower_bound = mid
    

So, if target is lower, upper_bound = mid-1 (its at the lower part of the array).

If the the element (B) is equal or greater then A[mid], we would set the lower_bound as mid (not mid+1, as this index could itself hold the upper range of the number).

Thats all folks!