Поиск в массиве целых чисел в определенном диапазоне

Question

Может ли кто-нибудь дать мне идеи по следующей проблеме?

Учитывая массив ar[] длины n и некоторые запросы, каждый запрос имеет форму a, b, c, найдите число с наименьшим индексом i таким, чтобы индекс находился в диапазоне [c, n], и таким, чтобы a < ar[i] < b.Всего (n - 1), c идет от 1 до n - 1.Ожидаемая сложность для каждого запроса должна составлять примерно O(log n), и подходит предварительное вычисление сложности не более O(n log n).Интуитивно понятно, что сегментное дерево пришло мне в голову, но я не мог придумать, как его построить и что оставить в каждом узле.

Answer 1

Хорошо, я подумал, что должен реализовать решение O(nlogn) / O(logn), которое я обсуждал с user12861.

Код работает путем построения n деревьев, по одному для каждого c.Каждое дерево делится большей частью своего содержимого с меньшими, с максимумом logn новых узлов.Таким образом, общая память и затраты времени на предварительную обработку ограничиваются O(nlogn).

. Фактические деревья очень похожи на интервальные деревья.Узлы хранят минимальное и максимальное значение, которое они охватывают, и наименьший индекс, который они содержат.Моя реализация, однако, не является самоуравновешивающей, но ее можно добавить, используя вашу любимую эвристику.

import sys

class Node:
    pass
class Interval(Node):
    def __init__(self,left,val,i,right):
        self.i = i; self.val = val
        self.left = left; self.right = right
        self.mini = min(left.mini, i, right.mini)
        self.min = min(left.min, val, right.min)
        self.max = max(left.max, val, right.max)
    def add(self,val,i):
        # We do naive inserting here. In a real worst case logn solution,
        # self-balancing would take place here.
        if (val,i) < (self.val,self.i): return Interval(self.left.add(val,i), self.val, self.i, self.right)
        if (self.val,self.i) < (val,i): return Interval(self.left, self.val, self.i, self.right.add(val,i))
        return self
    def query(self,a,b):
        # If the entire interval is covered, return mini, this is what keeps us
        # at max 2 opened nodes per level in the tree.
        if a <= self.min and self.max <= b: return self.mini
        # Otherwise compose an answer from the subtrees.
        res = sys.maxint
        if a <= self.val <= b: res = min(res, self.i)
        if self.left.min <= b and self.left.max >= a: res = min(res, self.left.query(a,b))
        if self.right.min <= b and self.right.max >= a: res = min(res, self.right.query(a,b))
        return res
class Tip(Node):
    def __init__(self):
        # This is a typical null-pattern idiom. The self.values are set to
        # the min/max identities to ensure to interference with the upwards
        # value propagation.
        self.mini = sys.maxint
        self.min = sys.maxint
        self.max = -sys.maxint
    def add(self,val,i):
        return Interval(Tip(), val, i, Tip())
    def query(self,a,b):
        return sys.maxint

# The input data array
data = [0, 3, 1, 2, 0, 4, 9, 6, 1, 7]
N = len(data)

# Build the array of trees. O(nlogn)
ar = [None]*N + [Tip()]
for i in range(N-1, -1, -1):
    ar[i] = ar[i+1].add(data[i],i)

# The query function. O(logn)
def query(a,b,c):
    return ar[c].query(a,b)

# Test
print query(2, 7, 4) # = 5

Answer 2

Я изменил технику Мэйсона Брайанта на что-то, что работает.Проблемы заключались в большем количестве ошибок в FindLowestIndex и более серьезной ошибке при поиске в дереве (оно может возвращать несколько результатов).

Несмотря на то, что эта работа все еще не решена, проблема на самом деле не решается.Настройка O(n log n) времени достаточно проста, но используя эту технику, я могу получить только O((log n)^2) время запроса.Интересно, есть ли у вас ссылка на исходную проблему в случае, если там есть дополнительные разъяснения?Или мне интересно, действительно ли проблема решаема?Или, может быть, O((log n)^2) означает "около" O(log n), поскольку проблема в любом случае меньше O(n).

Метод заключается в том, чтобы хранить наш массив в типичном дереве сегментов, но вместе с обычным сегментом.информацию мы также храним по порядку, все индексы элементов под каждым узлом.Это дополнительное хранилище занимает дополнительное O(n log n) время / пространство только в том случае, если вы правильно его добавили (n элементов хранятся на каждом из n уровней журнала), так что это никак не повлияет на время установки.Затем мы запрашиваем дерево, чтобы найти минимальный набор узлов, которые содержатся в нашем диапазоне (a, b).Этот запрос занимает примерно то же время, что и типичный запрос дерева сегментов (O(log n)), и находит не более 2 * log n совпадающих сегментов.По запросу мы находим самый низкий индекс в каждом соответствующем сегменте, который соответствует нашему ограничению c.Мы можем использовать бинарный поиск, чтобы найти этот индекс, так как мы держали индексы в порядке, поэтому для каждого соответствующего узла требуется O(log n) наихудший случай времени.Когда мы все сложим соответствующим образом, общее время составит O((log n)^2).

Дайте мне знать, какие шаги вы хотели бы уточнить.

C # Код:

void Test() {
  DateTime start;
  TimeSpan at = new TimeSpan(), bt = new TimeSpan();

  Random rg = new Random();
  for(int i = 0; i < 20; i++) {
    // build arrays from 5 to 10000 elements long, random values between 0 and 100
    // Break even time for queries is around 10000 elements in array for the values and queries used
    int[] array = (from n in Enumerable.Range(1, rg.Next(5, 10000)) select rg.Next(0, 100)).ToArray<int>();

    // Setup should be O(n log n) time/space
    ArraySearcher Searcher = new ArraySearcher(array);

    // Test each array a number of times equal to its length, with random values for a, b, c
    for(int j = 0; j < array.Length; j++) {
      int a = rg.Next(-1, 101), b = rg.Next(a, 102), c = rg.Next(0, array.Length);
      start = DateTime.Now;
      int expected = BruteSearch(array, a, b, c);
      at += DateTime.Now - start;
      // Search should be O(log n) time, but in reality is O((log n)^2) :(
      start = DateTime.Now;
      int got = Searcher.QuickSearch(a, b, c);
      bt += DateTime.Now - start;
      System.Diagnostics.Debug.Assert(got == expected);
    }
  }
  MessageBox.Show(at.ToString() + ", " + bt.ToString());
}

int BruteSearch(int[] array, int a, int b, int c) {
  for(int i = c; i < array.Length; i++)
    if(a < array[i] && array[i] < b)
      return i;
  return -1;
}

class ArraySearcher {

  SegmentNode Root;
  List<SegmentNode> Nodes;

  public ArraySearcher(int[] array) {
    Nodes = array.Select((value, index) => new SegmentNode(value, value, new List<int> { index }, null, null)).ToList<SegmentNode>();
    // Sorting will take us O(n log n)
    Nodes.Sort();
    // Creating a normal segment tree takes O(n log n)
    // In addition, in this tree each node stores all the indices below it in order
    // There are a total of n of these indices at each tree level, kept in order as we go at no extra time cost
    // There are log n levels to the tree
    // So O(n log n) extra time and space is spent making our lists, which doesn't hurt our big O notation compared to just sorting
    this.Root = SegmentNode.Merge(Nodes, 0, Nodes.Count - 1);
  }

  public int QuickSearch(int a, int b, int c) {
    return this.Root.FindLowestIndex(a, b, c);
  }

  class SegmentNode : IComparable {

    public int Min, Max;
    public List<int> Indices;
    public SegmentNode Left, Right;

    public SegmentNode(int Min, int Max, List<int> Indices, SegmentNode Left, SegmentNode Right) {
      this.Min = Min;
      this.Max = Max;
      this.Indices = Indices;
      this.Left = Left;
      this.Right = Right;
    }

    int IComparable.CompareTo(object other) {
      return this.Min - ((SegmentNode)other).Min;
    }

    public static SegmentNode Merge(List<SegmentNode> Nodes, int Start, int End) {
      int Count = End - Start;
      if(Start == End)
        return Nodes[Start];
      if(End - Start == 1)
        return SegmentNode.Merge(Nodes[Start], Nodes[End]);
      return SegmentNode.Merge(SegmentNode.Merge(Nodes, Start, Start + Count/2), SegmentNode.Merge(Nodes, Start + Count/2 + 1, End));
    }

    public static SegmentNode Merge(SegmentNode Left, SegmentNode Right) {
      int LeftCounter = 0, RightCounter = 0;
      List<int> NewIndices = new List<int>();
      while(LeftCounter < Left.Indices.Count || RightCounter < Right.Indices.Count) {
        if(LeftCounter < Left.Indices.Count && (RightCounter == Right.Indices.Count || Left.Indices[LeftCounter] < Right.Indices[RightCounter]))
          NewIndices.Add(Left.Indices[LeftCounter++]);
        else
          NewIndices.Add(Right.Indices[RightCounter++]);
      }
      return new SegmentNode(Left.Min, Right.Max, NewIndices, Left, Right);
    }

    public int FindLowestIndex(int SeekMin, int SeekMax, int c) {
      // This will find at most O(log n) matching segments, always less than 2 from each level of the tree
      // Each matching segment is binary searched in at worst O(log n) time
      // Total does indeed add up to O((log n)^2) if you do it right
      if(SeekMin < this.Min && SeekMax > this.Max)
        return FindLowestIndex(this.Indices, c);
      if(SeekMax <= this.Min || SeekMin >= this.Max)
        return -1;
      int LeftMatch = this.Left.FindLowestIndex(SeekMin, SeekMax, c);
      int RightMatch = this.Right.FindLowestIndex(SeekMin, SeekMax, c);
      if(LeftMatch == -1)
        return RightMatch;
      if(RightMatch == -1)
        return LeftMatch;
      return LeftMatch < RightMatch ? LeftMatch : RightMatch;
    }

    int FindLowestIndex(List<int> Indices, int c) {
      int left = 0, right = Indices.Count - 1, mid = left + (right - left) / 2;
      while(left <= right) {
        if(Indices[mid] == c)
          return c;
        if(Indices[mid] > c)
          right = mid - 1;
        else
          left = mid + 1;
        mid = left + (right - left) / 2;
      }
      if(mid >= Indices.Count)
        return -1;
      // no exact match, so return the next highest.
      return Indices[mid];
    }
  }
}

Answer 3

Первая попытка построить дерево из диапазонов.

Сначала вы найдете корень поддерева, в котором содержатся все решения запроса. Это довольно легко. Однако: это поддерево содержит некоторые значения вне набора решений.

Таким образом, чтобы найти наименьшее число, вы должны дважды пройти по дереву (от корня вниз по левой стороне дерева и снова от корня вниз по правой стороне). В каждой точке этих обходов вы будете проверять, нашли ли вы решение ниже, чем ваше предыдущее решение.

Когда это будет сделано, самое низкое решение в этом наборе будет самым низким.

Поскольку проверка решений каждого узла требовала бинарного поиска по списку индексов в этом поддереве, в конечном итоге вы работаете с O (ln (n) ^ 2), что слишком медленно.

Улучшение этого связано с тем, что это было бы легко, если бы мы всегда искали первый элемент в массиве. Тогда вам не нужно выполнять бинарный поиск, вы просто получаете первый элемент.

Чтобы добраться до этого места, вы должны построить n деревьев.

tree[0] has all values in the initializaing array
tree[1] has all but the first.
tree[2] has all but the first and second.

Таким образом, каждое из этих деревьев содержит единственное наилучшее решение.

Таким образом, поиск выполняется в O (ln (n)).

В примере кода мы позволили себе построить дерево, не реализовав собственные структуры данных.

Вы создаете массив узлов, делаете копию этого массива и сортируете одну из копий. Это работает в O (n ln (n)). Другая копия используется для поиска позиции в отсортированном массиве, поэтому вы можете удалять элемент каждый раз, когда строите другое дерево.

Конечно, можно удалить узел в связанном списке за постоянное время, но, поскольку у вас есть только ссылка на объект, я подозреваю, что реализация java должна искать в связанном списке элемент, подлежащий удалению, поэтому построение деревьев, вероятно, занимает O (n ^ 2) в этом примере. Легко исправить, хотя.

    public class ArraySearcher {

        public class SegmentNode implements Comparable<SegmentNode> {

            int min;
            int max;

            SegmentNode root;
            SegmentNode left;
            SegmentNode right;

            int lowIndex;

            public int compareTo(final SegmentNode obj)
            {
                return this.min - obj.min;

            }

            public boolean contains(final int n)
            {
                if ((n > this.min) && (n < this.max)) {
                    return true;
                } else {
                    return false;
                }
            }

            /**
             * Given the root of a tree, this method will find the center node. The
             * center node is defined as the first node in the tree who's left and
             * right nodes either contain solutions or are null.
             * 
             * If no node can be found which contains solution, this will return
             * null.
             * 
             * @param a
             * @param b
             * @return
             */
            public SegmentNode findCenter(final int a, final int b)
            {
                SegmentNode currentNode = this;

                while (true) {

                    /*
                     * first check to see if no solution can be found in this node.
                     * There is no solution if both nodes are
                     */
                    if ((a < currentNode.min && b < currentNode.min)
                            || (a > currentNode.max && b > currentNode.max)) {
                        return null;
                    }

                    /*
                     * Now check to see if this is the center.
                     */
                    if (((currentNode.left == null) || (a < currentNode.left.max))
                            && ((currentNode.right == null) || (b > currentNode.right.min))) {

                        // this is the center, return it.
                        return currentNode;

                    } else if ((currentNode.left == null)
                            || (a < currentNode.left.max)) {
                        // no solution on one side, is it in the left?
                        currentNode = currentNode.left;
                    } else {
                        currentNode = currentNode.right;
                    }
                }

            }

            public SegmentNode findLeft(final int seekMin)
            {
                /*
                 * keep going left until
                 */
                if ((this.min > seekMin)) {
                    return this;
                } else {
                    if (this.right == null) {
                        return null;
                    }
                    return this.right.findLeft(seekMin);
                }
            }

            /**
             * This method can be called on the center node. it traverses left
             * 
             * @param a
             * @param b
             * @return
             */
            public Integer findLeftmostLowestIndex(final int n)
            {
                if (null == this.left) {
                    return null;
                }

                int lowest = Integer.MAX_VALUE;
                SegmentNode current = this.left;

                // update the lowest with the right node if it is greater
                // than the current node.
                while (true) {

                    // collect the best value from the right and/or left
                    // if they are greater than N
                    if ((null != current.left) && (current.left.min > n)) {
                        lowest = current.left.lowIndex(lowest);
                    }
                    if ((null != current.right) && (current.right.min > n)) {
                        lowest = current.right.lowIndex(lowest);
                    }
                    if ((null == current.left) && (null == current.right)
                            && (current.max > n)) {
                        lowest = current.lowIndex(lowest);
                    }
                    // quit when we've gone as far left as we can
                    int seek = current.leftSeek(n);
                    if (seek == 0) {
                        break;
                    } else if (seek < 0) {
                        current = current.left;
                    } else {
                        current = current.right;
                    }

                }
                if (lowest == Integer.MAX_VALUE) {
                    return null;
                } else {
                    return new Integer(lowest);
                }

            }

            public SegmentNode findMatch(final int seekMin, final int seekMax)
            {
                if ((this.min > seekMin) && (this.max < seekMax)) {
                    return this;
                } else if ((this.min > seekMin) && (this.left != null)) {
                    return this.left.findMatch(seekMin, seekMax);
                } else {
                    if (this.right == null) {
                        return null;
                    }
                    return this.right.findMatch(seekMin, seekMax);
                }
            }

            public SegmentNode findMatchRight(final int seekMin, final int seekMax)
            {
                if ((this.min > seekMin) && (this.max < seekMax)) {
                    return this;
                } else if (this.max < seekMax) {
                    if (this.right == null) {
                        return null;
                    }
                    return this.right.findMatchRight(seekMin, seekMax);
                } else {
                    if (this.left == null) {
                        return null;
                    }
                    return this.left.findMatchRight(seekMin, seekMax);
                }
            }

            /**
             * Search for the first number in the tree which is lower than n.
             * 
             * @param n
             * @return
             */
            public Integer findRightmostLowestIndex(final int n)
            {
                if (null == this.left) {
                    return null;
                }

                int lowest = Integer.MAX_VALUE;
                SegmentNode current = this.right;

                // update the lowest with the right node if it is greater
                // than the current node.
                while (true) {

                    // collect the best value from the right and/or left //this.max
                    // < b
                    // if they are greater than N
                    if ((null != current.left) && (current.left.max < n)) {
                        lowest = current.left.lowIndex(lowest);
                    }
                    if ((null != current.right) && (current.right.max < n)) {
                        lowest = current.right.lowIndex(lowest);
                    }
                    if ((null == current.left) && (null == current.right)
                            && (current.min < n)) {
                        lowest = current.lowIndex(lowest);
                    }

                    // quit when we've gone as far left as we can
                    int seek = current.rightSeek(n);
                    if (seek == 0) {
                        break;
                    } else if (seek < 0) {
                        current = current.left;
                    } else {
                        current = current.right;
                    }

                }
                if (lowest == Integer.MAX_VALUE) {
                    return null;
                } else {
                    return new Integer(lowest);
                }
            }

            /**
             * 
             * @param seekMin
             * @param seekMax
             * @return
             */
            public SegmentNode findSegmentRoot(final int seekMin, final int seekMax)
            {

                return null;
            }

            public int leftSeek(final int n)
            {
                if ((null == this.left) && (null == this.right)) {
                    return 0;
                    // } else if ((null != this.left) && (this.left.max > n)) {
                } else if ((null != this.left) && ((n < this.left.max))
                        || (this.left.contains(n))) {
                    return -1;
                    // } else if ((null != this.right) && (this.right.min <= n)) {
                } else if ((null != this.right) && ((n >= this.right.min))) {
                    return +1;
                } else {
                    return 0;
                }
            }

            public int rightSeek(final int n)
            {
                if ((null == this.left) && (null == this.right)) {
                    return 0;
                } else if ((null != this.left) && (this.left.max >= n)) {
                    return -1;
                } else if ((null != this.right) && (this.right.min < n)) {
                    return +1;
                } else {
                    return 0;
                }
            }

            @Override
            public String toString()
            {
                StringBuilder value = new StringBuilder();
                if (null != this.left) {
                    value.append("{ { " + this.left.min + ", " + this.left.max
                            + "} }, ");
                } else {
                    value.append("{ " + this.min + " }, ");
                }

                if (null != this.right) {
                    value.append("{ { " + this.right.min + ", " + this.right.max
                            + "} }");
                } else {
                    value.append("{ " + this.max + " }, ");
                }
                return value.toString();
            }

            private int lowIndex(final int lowest)
            {
                if (lowest < this.lowIndex) {
                    return lowest;
                } else {
                    return this.lowIndex;
                }
            }
        }

        public static int bruteForceSearch(final int[] array, final int a,
                final int b, final int c)
        {
            // search from c onward

            /**
             * search for the first value of the array that falls between a and b
             * ignore everything before index of c
             */
            for (int i = c; i < array.length; i++) {
                if ((a < array[i]) && (array[i] < b)) {
                    return i;
                }
            }
            return -1;
        }

        SegmentNode[] trees;

        public ArraySearcher(final int[] array)
        {
            buildTree(array);
        }

        public void buildTree(final int[] array)
        {
            ArrayList<SegmentNode> mNodes = new ArrayList<SegmentNode>();
            for (int i = 0; i < array.length; i++) {
                SegmentNode mCurrentNode = new SegmentNode();
                mCurrentNode.lowIndex = i;
                mCurrentNode.min = array[i];
                mCurrentNode.max = array[i];
                mNodes.add(mCurrentNode);
            }
            ArrayList<SegmentNode> unsortedClone =
                    new ArrayList<SegmentNode>(mNodes);

            // n (ln (n) )
            Collections.sort(mNodes);

            LinkedList<SegmentNode> nodesList = new LinkedList<SegmentNode>(mNodes);

            this.trees = new SegmentNode[nodesList.size()];
            for (int i = 0; i < this.trees.length; i++) {
                this.trees[i] = merge(nodesList, 0, nodesList.size() - 1);

                // we remove the ith one at each iteration
                nodesList.remove(unsortedClone.get(i));
            }
        }

        /**
         * 
         * @param nodes
         * @param i
         * @param j
         * @return
         */
        public SegmentNode merge(final List<SegmentNode> nodes, final int i,
                final int j)
        {
            if (i > j) {
                throw new AssertionError();
            }
            SegmentNode left;
            SegmentNode right;
            int count = j - i;

            if (count == 1) {
                SegmentNode mParent = merge(nodes.get(i), nodes.get(i + 1));
                return mParent;
            } else if (count == 0) {
                return nodes.get(i);
            } else {
                int mid = (count / 2) + i;
                left = merge(nodes, i, mid);
                right = merge(nodes, mid + 1, j);
            }
            return merge(left, right);
        }

        /**
         * Build a parent segment from two other segments.
         * 
         * @param a
         * @param b
         * @return
         */
        public SegmentNode merge(final SegmentNode a, final SegmentNode b)
        {
            SegmentNode parent = new SegmentNode();
            parent.root = parent;
            parent.min = a.min;
            parent.left = a;
            parent.max = b.max;
            parent.right = b;

            if (a.lowIndex > b.lowIndex) {
                parent.lowIndex = b.lowIndex;
                b.root = parent;
            } else {
                parent.lowIndex = a.lowIndex;
                a.root = parent;
            }

            return parent;
        }

        /**
         * The work horse, find all the points with indexes greater than c that lie
         * between a and b.
         * 
         * @param a
         * @param b
         * @param c
         * @return
         */
        public Integer search(final int a, final int b, final int c)
        {
            if (c < this.trees.length) {
                SegmentNode root = this.trees[c];

                if ((a > root.max) || (b < root.min)) {
                    return null;
                }

                SegmentNode center = root.findCenter(a, b);
                if (null == center) {
                    return null;
                }

                // special case to deal with a node with no children.
                if ((center.left == null) && (center.right == null)) {
                    if ((a < center.min) && (b > center.max)) {
                        return new Integer(center.lowIndex);
                    } else {
                        return null;
                    }
                }

                Integer right = center.findRightmostLowestIndex(b);
                Integer left = center.findLeftmostLowestIndex(a);

                if ((null == right) && (null == left)) {
                    return null;
                } else if (null == right) {
                    return left;
                } else if (null == left) {
                    return right;
                } else if (right.compareTo(left) > 0) {
                    return left;
                } else {
                    return right;
                }

            } else {
                return null;
            }
        }
    }

кстати, я до сих пор использую подобные тесты, чтобы проверить его на основе подхода грубой силы:

    static void testBoth(final int[] array, final ArraySearcher searcher,
            final int a, final int b, final int c)
    {
        System.out.println("ArraySearcherTest.testBoth(array, mSearcher, " + a
                + ", " + b + ", " + c + ");");
        int expected = ArraySearcher.bruteForceSearch(array, a, b, c);
        Integer calcObj = searcher.search(a, b, c);
        int calcInt = -1;
        if (null != calcObj) {
            calcInt = calcObj.intValue();
        }
        assertEquals(expected, calcInt);

    }

    @Test
    public void randomizedProblemTester()
    {
        for (int i = 0; i < 100; i++) {
            // build arrays from 5 to 20 elements long
            int[] array = new int[TestUtils.randomInt(5, 20)];
            System.out.print("int[] array = {");
            for (int j = 0; j < array.length; j++) {
                // with values from 0 to 100
                array[j] = TestUtils.randomInt(0, 100);
                System.out.print(array[j] + ", ");
            }
            System.out.println("};");

            ArraySearcher mSearcher = new ArraySearcher(array);
            for (int j = 0; j < array.length; j++) {
                int a = TestUtils.randomInt(0, 100);
                int b = TestUtils.randomInt(a, 100);
                int c = TestUtils.randomInt(0, 20);
                ArraySearcherTest.testBoth(array, mSearcher, a, b, c);
            }

        }


   }

Answer 4

Вы уже прошли это? Полагаю, это поможет вам понять структуру и придумать способ ее построения. Остальные могут быть сравнениями.

Answer 5

Если я правильно читаю, есть n-1 запросов с изменением только c. В таком случае, почему вы не решаете запросы задом наперед?сначала возьмем последний запрос, так как он включает в себя последний элемент проверки массива, если элемент находится между a и b, если это так, сохраните результат в массиве ans [n-1] = n-1, иначе давайте поместим ans [n-1] =-1, для любого следующего запроса j от n-2 до 0

if a[j] is not between a and b 
     ans[j] = ans[j+1] 
else 
     ans[j] = j

все это можно сделать в O (n).

Answer 6

Построить массив индексов и отсортировать их. То есть, учитывая массив [20, 0, 10, 15, 5], вы бы создали начальный массив [0, 1, 2, 3, 4]. Теперь вы сортируете массив индексов, чтобы отразить элементы в порядке сортировки. Сортированный индекс будет [1, 4, 2, 3, 0]. Вы получите два массива:

original = [20, 0, 10, 15, 5]
tag = [1, 4, 2, 3, 0]

Вы можете выполнить двоичный поиск исходного массива через массив тегов. То есть ваша функция сравнения сравнивает original[tag[x]] и original[tag[y]]. Это решает проблему «где индекс». Затем вы можете использовать бинарный поиск в сегменте tag[c] ... tag[n].

Похоже, это должно работать. Вам потребуется стабильная сортировка, чтобы равные числа сохраняли свой относительный порядок.

Answer 7

Возможно, я что-то упустил.Разве это не удовлетворяет вашим требованиям?

for (int i = c; i < n; i++)
{
    if (a < ar[i] && ar[i] < b)
        return i;
}