0

考虑到我有一个排序数字数组，偏移量为 0 到 N-1，其中 N 是数组的长度。完全排序的数组的零偏移量为 0，如下所示

[1, 2, 4, 11, 15, 19, 26]

数组[19, 26, 1, 2, 4, 11, 15]的偏移量为 2，因为较小的数字从第二个索引开始并环绕到第一个。

分配问题是如何在数组中找到数字的索引。对于排序数组，解决方案显然是通过二进制搜索来查找索引（有或没有递归）。

如何在具有偏移量的数组中找到数字的索引？偏移量未知。我想要一个解决方案的大纲，我会尝试用我熟悉的语言来实现它。

4

1 回答 1

0

使用三元搜索找到数组的最大元素。所以让我们假设 X 是数组中最大元素的索引。因此，如果 ，则偏移量将为 X+1，X < N-1否则偏移量 = 0。

然后您可以对 eash 元素进行两次二进制搜索以找到该数字的索引。第一个将在 from 范围内运行，0 - (offset-1)第二个将在 之间运行offset - N。如果您被允许使用更多空间，那么您还可以将数组附加到自身，然后为每个查询进行一次二进制搜索offset - (N+offset-1)

于 2013-08-18T19:34:53.037 回答