Modify binary search to find all integers in an array bigger than x and less than 2x with a time- complexity better than O(n)

Question

Let A be a sorted array containing n distinct positive integers. Let x be a positive integer such that both x and 2x are not in A.

Describe an efficient algorithm to find the number of integers in A that are larger than x and smaller than 2x

what is the complexity of the algorithm? can someone write a pseudo code without using libraries?

I know this can be done with a linear time complexity but binary search could be modify to achieve this. The following is the linear time complexity solution I came up with

def find_integers(A, x):
    integers = 0
    for element in A:
        if element > x and element < 2*x:
            integers += 1
    return integers 

Answer 1

I'm on a bit of a mission to improve everybody's default binary search. As I described in this answer: How can I simplify this working Binary Search code in C? ...

...pretty much all of my binary searches search for positions instead of elements, since it's faster and easier to get right.

It's also easily adaptable to situations like this:

def countBetweenXand2X(A,x):
    if x<=0:
        return 0

    # find position of first element > x

    minpos = 0
    maxpos = len(A)
    while minpos < maxpos:
        testpos = minpos + (maxpos-minpos)//2
        if A[testpos] > x:
            maxpos = testpos
        else:
            minpos = testpos+1

    start = minpos;

    # find position of first element >= 2x

    maxpos = len(A)
    while minpos < maxpos:
        testpos = minpos + (maxpos-minpos)//2
        if A[testpos] >= x*2:
            maxpos = testpos
        else:
            minpos = testpos+1

    return minpos - start

This is just 2 binary searches, so the complexity remains O(log N). Also note that the second search begins at the position found in the first search, since we know the second position must be >= the first one. We accomplish that just by leaving minpos alone instead of resetting it to zero.