arrays - 数组的一部分被反转时的二进制搜索

Question

给定一个数组(大小为 N)(已排序但其中的某些部分被反转)和一系列元素 (Q)，我们必须根据元素是否存在于数组中来输出是/否。

我想出的解决方案如下:

1. 做一个线性遍历，找出数组被反转的索引。
2. 对于每个元素的查询，在 3 个子数组(第一个子数组、反向子数组和剩余子数组)上调用二分查找

时间复杂度是O(N + Q* log N)。我想知道我们是否可以在O(Q * Log N)中避免第一步？

Answer 1

你知道数组由三部分组成，升序、降序、升序。所以你可以通过采样找到这两个临界点。这有点棘手，一旦你在反向部分找到一个点，它就很容易了(只需两次二进制搜索)。找到反向部分更难。如果我们采样并且 array[i+1] < array[i]，我们就找到了。但是如果错过了，就不知道是太高了还是太低了，所以我们需要一个有间隔的队列来测试。我们从一个区间开始，对中间区间进行采样。这给了我们两个区间，所以我们对中间的区间进行采样，这给了我们四个区间，依此类推，直到我们找到反向部分的索引。