给定一个正整数序列和一个整数 M，返回序列中第一个大于 M 的数(如果不存在则返回 -1)。
示例:序列 = [2, 50, 8, 9, 1], M = 3 -> return = 50
每个查询所需的 O(log n)(预处理后)。
我考虑过 BST，但是给定一个升序序列我只会得到一条很长的路径，这不会给我 O(logn) 时间...
编辑:使用的结构也应该易于修改，即应该可以用给定的元素替换找到的元素并重复搜索另一个 M(除预处理之外的所有内容 - O(logn))。当然，如果我可以将“先大”更改为“先小”并且不必在算法中进行太多更改，那就太好了。如果有帮助，我们可以假设所有数字都是正数并且没有重复。
最佳答案
创建第二个数组(设为 aux )，其中每个元素 i : aux[i] = max { arr[0],arr[1], ... ,arr[i]} (原始数组中索引为 j <= i 的所有元素的最大值)。
很容易看出这个数组是自然排序的，对aux进行简单的二分查找将产生所需的索引。 (如果元素不存在，则通过二分查找很容易找到比请求元素大的第一个元素)。
时间复杂度为O(n)预处理(只做一次)和O(logn)每个查询。
关于algorithm - 在未排序的序列中找到第一个大于给定数字的数字，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13780342/