Insert an element in sorted and rotated list

Question

A list of sorted and rotated element is given. Elements are either sorted in ascending or descending order. For example - I've list of sorted elements as follows

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

Now this list is rotated by X number of times and then it looks as follows.

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

If you want to insert an element in this list what would be the most efficient method to do it.

For element to be inserted is 13, If list is traversed in a linear fashion, false insertion may happen between 59 and 10.

I'm not expecting any code, rather discussion of algorithm is what I'm looking forward to. Value 21 can be inserted as either first /last element. Account for boundary condition such as - to be inserted element, the first and last element are of same value.

Answer 1

Keep track of the minimum element during the X 'rotations'. Then use binary search in the relevant half.

Answer 2

Assuming that your list allows efficient random access this is a binary search with a offset. If you've found the right index you move the element 1 index position to the left. This has complexity O(log n) for the search and O(n) for the list copy operation.

Answer 3

One the solution I came up with,

1.Check for boundary conditions such as

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

If any of the above conditions are met insert element at the the first place.

2.Take the middle element

• check if new element == Middle element - insert new element at this position
• Check Is new element is b/w Middle element and Right most OR it is b/w Left most and Right most element.

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

• If number of elements are <= 2, insert new element b/w Left-Middle OR Right-Middle
• Otherwise compute new Left, Middle and Right element and perform step 2.

Answer 4

The real question of course, is about the data-structure and efficiency required.

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

Note that you need to know about the ordering, otherwise 4,2 could be interpreted either as:

• 2,4 ascending and rotated once
• 4,2 descending

From 3 elements, you can guess 4,2,3 is ascending and rotated once because of the way the maximum and minimum values are set together.

Indeed, you should probably use a Circular structure, which would make rotation easy. Then you can maintain an Accessor to this structure:

• Which points to the minimum
• Which points to the current beginning

Given the minimum, it's easy (one comparison to its right-hand neighbor) to know what the ordering is. And from that point on, insertion in the Circular structure is easy too.

Answer 5

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

1. Use binary search to find the biggest / smallest element of the list. This takes O(logN). Implementation is easy just compare the element you are looking at with the first element of the list.
2. Use binary search to insert the new element, using only the necessary part of the list. This takes O(logN) as well.

More on point 1: Say you need to find the biggest element in 51,53,54,59,10,12,14,16,18,20.

First you pick the middle element (say it would be 12). 12 is smaller than 51, therefore the biggest element is on the left from 12. You split the interval in half, and get 54. 54 is greater than 51, therefore the biggest element is between 54 and 12. And so on