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

I don't think so we can achieve with the Binary Search with linear time complexity. — Py-Coder, Feb 13 '19 at 02:39

score 2 · Answer 1 · answered Feb 13 '19 at 02:35

2

As you already found out you can use binary search. Search for x and 2x and note the positions in the list, you can calculate the number of integers from the differnce between the two positions.

Since you are using python, the bisect module can help you with binary search.

answered Feb 13 '19 at 02:35

krisz

2,686
2
11
18

do you have an idea how the binary search algorithm would be structured like? I need to write a pseudo code – edogado Feb 13 '19 at 02:40
@edogado: Just Google `binary search sorted array`. krisz's answer provides everything else you need. – ruakh Feb 13 '19 at 03:11

Matt Timmermans · Accepted Answer · 2019-02-13T03:40:00.467

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.

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)

2 Answers2