Insert an item in a sorted and rotated list

Question

A list of the sorted and rotated item is given. Items are sorted in ascending or descending order . For example, I have a list of sorted items as follows

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

Now this list is rotated X times, and then looks like this.

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

If you want to insert an item into this list, that would be the most efficient method for doing this.

The item to be inserted is 13. If the list moves linearly, false insertion may occur between 59 and 10.

I do not expect any code, rather a discussion of the algorithm is what I look forward to. The value 21 can be inserted as the first / last element. Consideration of boundary conditions, such as: - the inserted element, the first and last elements have the same value.

Answer 1

This can be solved in log (N) time. In short:

• Use binary search to find the largest / smallest item in the list. This takes O (logN). The implementation simply compares the item you are viewing with the first item in the list.
• Use binary search to insert a new item using only the desired part of the list. It also accepts O (logN).

More on point 1: Let's say you need to find the largest element at 51,53,54,59,10,12,14,16,18,20.

First you select the middle element (let's say it will be 12). 12 is less than 51, so the largest element is to the left of 12. You divide the interval in half and get 54. 54 is greater than 51, so the largest element is between 54 and 12. And so on

Answer 2

The real question, of course, is data structure and performance.

• What is ordering (ascending / descending)
• Where is the "minimum"

Please note that you need to know about the order, otherwise 4,2 can be interpreted as:

• 2,4 ascending and in turn
• 4,2 descending

Of the 3 elements, you can assume that 4,2,3 rises and rotates once due to the fact that the maximum and minimum values ​​are set together.

In fact, you should probably use a circular structure that makes rotation easier. Then you can support Accessor in this structure:

• Which indicates a minimum
• Which indicates the current start

Given the minimum, it is easy (one comparison with his right neighbor) to know what order is. And from now on, embedding in a circular structure is also easy.

Answer 3

Keep track of the minimum element during X-revolutions. Then use binary search in the corresponding half.

Answer 4

Assuming your list allows efficient random access, this is an offset binary search. If you find the index you want, you move the index position of element 1 to the left. This has the complexity of O (log n) for searching and O (n) for copy list operation.

Answer 5

One of the solutions I came across is

1.Check the boundary conditions, such as

• If the new element is b / w the first and last OR element is vice versa
• If the new item is equal to the first or last item

If any of the above conditions is met, insert the item first.

2.Select the middle item

• check if new element == Middle element - insert a new element at this position
• Check that the new element is the black and white element Middle and Right most OR , it is b / w the most right and leftmost element.

3.Compute number of element b / w Left-Middle OR Middle right based on the above conditions.

• If the number of elements is <= 2, add a new element b / w Left-Middle OR Right-Middle
• Otherwise, compute the new Left, Middle, and Right element and complete step 2.