在范围内找到大于x的数字 [英] Finding a number greater than x in a range

问题描述

我有一个问题，经过一些修改后，该问题简化为在范围[l，r]中找到大于x的最小索引

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

例如：假设数组 A = {1、2、3、6、9、8、4、3、7、6、2}

，查询为 在范围[2，6]中找到大于或等于5的数组A中元素的最小索引

上述查询的答案是4（此索引的值是6）（索引基于1）

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)

是否有一种算法可以在O（logN）中查询，其中N为否。

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

推荐答案

实际上，有很多方法可以在构建后以O（log N）时间支持查询

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.

• 按照索引的顺序，将以A的元素作为叶子的二叉树。


• 在每个内部节点的子树中，记录叶子的最大值


• 您需要能够找到给定索引的节点路径。如有必要，请记录每个内部节点中第一片叶子的索引。


• 现在，找到最小索引> = L且值> = X的最小索引：
  
  
  
  
  • 在树中找到A [L]的路径
  
  
  • 如果A [L]< X，然后上树，直到找到一个包含值> = X的右叔父。 b $ b
  • 下移叔父树，找到值> = X的第一片叶子。下降时，如果左孩子的叶子> = X（检查存储的最大值），则向左走。否则就去吧。
  
  
  • 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.

    要使上述算法真正有效，您可以像对堆一样将树编码为数组。在此表示形式中（使用基于1的索引），您有一个数组，其中包含N-1个内部节点的最大值，然后依次排列N个叶子。将该数组称为 H 。然后 H [i] 的子代位于 H [i * 2] 和 H [i * 2 + 1] 。 H [i] 的父级位于 H [i>> 1]

    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]

    在伪代码中，使用基于1的索引：

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

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

    我们像这样构建H：

    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.

    现在，查询功能：

    //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);
    

    这满足了O（log N）时间查询的要求。当您知道答案不会少于 maxindex 时，最好早点退出（不是太困难），但这会使伪代码不太清楚，所以我将其保留为练习

    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

    这篇关于在范围内找到大于x的数字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！