Finding a number greater than x in a range

Question

I have a problem which after some modifications reduces to "Finding the least index of number greater than x in a range[l, r] "

For example: Suppose an array A = {1, 2, 3, 6, 9, 8, 4, 3, 7, 6, 2}

And the query is "find least index of element in array A in range [2, 6] which is greater or equal to 5"

Answer for the above query is 4(value for this index is 6)(Indices are 1 based)

There are multiple queries, array is not sorted(consider that input is already in memory)

Is there an algorithm in which query is possible in O(logN) where N is no. of elements in array A.

Answer 1

There are actually a bunch of ways to support queries in O(log N) time after building a data structure that takes O(N) space.

Easy to understand answer

• Make a binary tree with the elements of A as the leaves, ordered by index.
• In each internal node, record the maximum value of leaves in its subtree
• You need to be able to find the path to a node given its index. If necessary, record the index of the first leaf in each internal node. You can get away without this by building your tree with a convenient shape.
• Now, to find the least index >= L with a value >= X:
  • Find the path in the tree to A[L]
  • If A[L] < X, then go up the tree until you find a right uncle that contains a value >= X
  • Go down the uncle tree to find the first leaf with value >=X. While descending, if the left child has a leaf >= X (check the stored max value), then go left. Otherwise go right.

Super-Efficient Answer

To make the above algorithm really efficient, you can encode the tree into an array, like we do for heaps. In this representation (using 1-based indexes), you have an array containing the maximum values for N-1 internal nodes, followed by the N leaves in order. Call that array H. Then the children of H[i] are at H[i*2] and H[i*2+1]. The parent of H[i] is at H[i>>1]

In pseudocode, using 1-based indexes, we are given:

A[] = input array, N = input array size

We build H like this:

H = new array with size N*2-1, indexed from 1 to N*2-1
for (int i=1; i<=N; ++i)
    H[i+N-1]=A[i];
for (int i=N-1; i>0; --i)
    H[i] = max(H[2*i],H[2*i+1]);

Note that we create the children before the parents so that the children are there when we need to get the maximum of their values.

Now, the query function:

//get the index of the first element with val >= minval, index >= minindex, and index <= maxindex
//returns -1 if there is no such element

firstAtLeast(minval, minindex, maxindex)

    if (maxindex < minindex)
        return -1;

    node = minindex+N-1; //find minindex in the tree

    //go up and right until we find a subtree that has a value >= minval

    while(H[node] < minval)

        //if we are a right child of our parent, go up until
        //we have a right sibling
        while( (node&1) == 1 ) //node is odd
            node = node>>1;    //same as floor(node/2);
            if (node <= 1)
                //we went up to the root
                //there is no such element
                return -1;

        //now node is a left child.  try its right sibling        
        ++node;

    //We found a subtree.  get the first valid leaf

    while(node < N) //while it's an internal node
       node = 2*node; //left child of the node
       if (H[node] < minval)
           ++node;  //left child not valid - move to right child

    //Found leaf.  get index in A[i] and check against maxindex

    index = node-(N-1);
    return (index <= maxindex ? index : -1);

This satisfies the requirement for queries in O(log N) time. It would be nice (and not too difficult) to exit early when you know there won't be an answer less than maxindex, but that would make the pseudocode a little less clear, so I'll leave it as an exercise