Question

give an algorithm where given as input an array A[1...n] with the following property. There exists an index I such that if we append A[1...i−1] after A[i...n], we get an array in sorted increasing order. For simplicity you can assume that n is a power of 2.

Give an efficient algorithm that returns the smallest element in A. Analyze the time complexity of your algorithm.

Hint: you may want to compare A[1] and A[n/2].

Answer 1

If you read this question carefully you will know that this case occurs when you left rotate the array a certain number of times. for example, if you have a sorted array 1 2 3 4 5 6 7 and you circularly rotate the array twice to its left you get the array 3 4 5 6 7 1 2,

considering 0 based indexing, here for i = 5 we have the first part as 3 4 5 6 7 and the second part as 1 2, if we append the first part after the end of the second part you get a sorted array.

A fairly simple algorithm to achieve this is,

Find the minimum element by iterating the entire array once, the index of the minimum element is the value of i that you need. How does this work?
This works because the minimum element should be at the first position, so you make the second array start from this index and hence this value of i is the answer.

The time complexity of this algorithm is O(N) since in the worst case you might need to iterate over the entire array.

No we can modify the classic binary search algorithm to improve the time complexity of the problem. We can achieve the lask in O(logN) using a modified variant of binary search, let us see how.

• if you notice, the minimum element is the only one which has its previous value greater that its own value. if we are unable to find any such element then the array is already sorted. So our major task ends up at finding te minimum element in the array. We find the middle element by comparing it with the element present at the (middle -1)th index and (middle +1)th index
• If the element at the middle index is not the minimum element then it is present in either the left half or the right half.
  1. If middle element is smaller than last element, then the minimum element lies in left half.
  2. Otherwise the minimum element lies in right half.

This is the algorithm that would find the value of a suitable i in O(logN) time. I have provided a pseudo code also, have a look.

Here is the algorithm in textual form:

// the function that finds the element with the minimum value.
function findIndexI (int values[], int lo, int hi) :

       // Base condition, if the first element is less than the last
       // element, then it would mean that the values array is already soted
       if a[lo] < a[hi]
            return lo

        // Base condition, if there is only one element
   if (hi == lo) return values[lo]

   // store the middle index
        mid := (lo+hi) / 2
     
   // Condition when element at index (mid+1) is minimum
   if mid < hi && values[mid + 1] < values[mid]
       return values[mid + 1]
  
   // Condition when element at index (mid) is minimum
   if mid > lo && values[mid] < values[mid - 1]
       return values[mid];
  
   // if the mid value is less than the last element
   // the the result is in the left half, otherwise
   // it is in the right half.
   if (values[hi] > values[mid])
       return findIndexI(values, lo, mid - 1)

      else
          return findIndexI(values, mid + 1, hi)