algorithm - 在未排序的序列中找到大于给定数字的第一个数字

Question

给定一个正整数序列和一个整数 M，返回序列中大于 M 的第一个数（如果不存在则返回 -1）。

示例：序列 = [2, 50, 8, 9, 1], M = 3 -> 返回 = 50

每个查询所需的 O(log n)（预处理后）。

我想到了 BST，但是给定一个升序，我只会得到一条很长的路径，这不会给我 O(logn) 时间......

编辑：使用的结构也应该易于修改，即应该可以用给定的元素替换找到的元素并重复搜索另一个 M（一切 - 除了预处理 - O（logn））。当然，如果我可以将“第一个更大”更改为“第一个更小”并且不必在算法中进行太多更改，那就太好了。如果有帮助，我们可以假设所有数字都是正数并且没有重复。

Answer 1

创建第二个数组（让它成为aux），其中每个元素i：（原始数组中aux[i] = max { arr[0],arr[1], ... ,arr[i]}具有索引的所有元素的最大值）。j <= i

很容易看出这个数组是按性质排序的，简单的二分搜索aux就会产生所需的索引。（如果元素不存在，通过二分搜索很容易获得大于请求元素的第一个元素）。

时间复杂度是O(n)预处理（只做一次）和O(logn)每个查询。