algorithm - 在排序和旋转列表中插入一个元素

Question

给出了一个排序和旋转元素的列表。元素按升序或降序顺序排序。例如 - 我有如下排序元素列表

10,12,14,16,18,20,51,53,54,59

现在这个列表被旋转 X 次，然后它看起来如下。

51,53,54,59,10,12,14,16,18,20

如果您想在此列表中插入一个元素，最有效的方法是什么。

对于要插入的元素为13，如果以线性方式遍历列表，则可能会在59到10之间发生错误插入。

我不期待任何代码，我期待的是对算法的讨论。 值 21 可以作为第一个/最后一个元素插入。考虑边界条件，例如 - 要插入的元素，第一个和最后一个元素具有相同的值。

Answer 1

这可以在 log(N) 时间内解决。简而言之:

1. 使用二进制搜索找到列表中最大/最小的元素。这需要 O(logN)。实现很简单，只需将您正在查看的元素与列表的第一个元素进行比较即可。
2. 使用二进制搜索插入新元素，只使用列表的必要部分。这也需要 O(logN)。

关于第 1 点的更多信息: 假设您需要找到 51,53,54,59,10,12,14,16,18,20 中最大的元素。

首先你选择中间的元素(假设它是 12)。 12小于51，所以最大的元素在12的左边。你把区间分成两半，得到54。54大于51，所以最大的元素在54和12之间。依此类推