給出了一個排序和旋轉元素的列表。元素排序爲升序或降序訂單。例如 - 我排序的元素列表如下在排序和旋轉列表中插入一個元素
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