给出了一个排序和旋转元素的列表。元素排序为升序或降序订单。例如 - 我排序的元素列表如下在排序和旋转列表中插入一个元素
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可以作为第一个/最后一个元素插入。考虑边界条件，例如 - 要插入的元素，第一个元素和最后一个元素具有相同的值。
这可以在log（N）时间内解决。总之：
更多关于第1点： 假设您需要找到51,53,54,59,10,12,14,16,18,20中最大的元素。
首先你选择中间元素（假设它是12）。 12小于51，因此最大的元素是从左边开始的12.你将区间分成两半，得到54.54大于51，因此最大元素在54和12之间。等等。
请解释如何通过二分查找从列表'51,53,54,59,10,12,14,16,18,20'中解析'59'。 – kennytm 2010-02-19 13:37:01
请参阅我的编辑。 – Olexiy 2010-02-22 15:13:45
您需要假定所有元素都是不同的或类似的;在由n-1个零和1个输入组成的输入中很难找到它。 – user287792 2010-03-18 16:41:05
跟踪X'旋转'期间的最小元素。然后在相关的一半中使用二进制搜索。
这个问题假设你不是做轮转的人:) – Olexiy 2010-02-22 15:15:13
@Olexiy：是的。但是经常治疗原因要好于治疗症状;） – 2010-02-23 00:19:58
假设您的列表允许有效的随机访问，这是一个带偏移量的二分查找。如果您找到了正确的索引，则将元素1索引位置移动到左侧。这具有用于搜索的复杂性O（log n）和用于列表复制操作的O（n）。
一个我想出了解决方案，
1.检查为边界条件，如
如果满足上述条件中的任何一个，则首先插入元素。
2.Take中间元素
3.元素b/w左侧中间或中间右侧根据上述条件。
真正的问题当然是关于数据结构和效率的要求。
请注意，您需要了解订货，否则4,2可以解释无论是作为：
2,4升序和旋转一次4,2降从3个元素中，可以猜出4,2,3是上升和旋转一次，因为最大值和最小值被设置在一起。
事实上，你应该使用圆形结构，这将使旋转变得容易。然后你就可以维持一个访问这个结构：
考虑到最小，很容易（一个比较其右手邻居）知道排序是什么。从那时起，插入圆形结构也很容易。
它是一个*链表*（其中随机访问是不可能的）或一个*数组*（其中随机访问是可能的）？ – kennytm 2010-02-19 13:37:40