Coding algorithms: Array rotation

Problem:

A sorted array has been rotated so that elements might appear in the order 3 4 5 6 7 1 2. How do you find the minimum element? You may assume the array has unique elements.

Solution:

Analyze the problem to select an approach:
Let's first look at the information we already have from the problem definition itself. We got two things:

1. We have a sorted array.
2. It is rotated.
   Now lets think of possibilities to understand if there are any inherent complexities in our problem. It is given to us that it is a sorted array. Sorting can happen in ascending order or descending order. Would our approach in solving the problem be different if the order was changed? Yes and no. Depends on from where we are looking (if you feel utterly confused by this statement, wait for the explanation in the end under- Extending the boundaries of the algorithm). For now lets just assume that we answered a 'Yes' to that question (any normal person would). If the array is in ascending order, we are expecting input values to increase and then suddenly find a smaller value. For a descending ordered array it would be vice versa. So we need to decide what we are expecting in the input. Since the example sample in the problem is in ascending order, lets assume that to be true and just remember that our solution makes an assumption that the sorted array is in ascending order. And that as of now we have no idea of how we are approaching the problem if we did not know about that. So far what is the takeaway in this discussion? When you do not seem to have all the information to develop an approach, you make an assumption.
   Assumption: Input array sorted in ascending order.

Now let's talk about the rotation. What are the possibilities? Rotation can be clockwise or counter-clockwise. Let's see if rotating the array clockwise vs anticlockwise would make a difference in how we approach the problem. Lets start with the same set of noes: 1 2 3 4 5 6 7
Rotating clockwise by 2 noes: 6 7 1 2 3 4 5
Rotating anticlockwise by 2 noes: 3 4 5 6 7 1 2
In both cases we see that the occurrence of the oddity -a smaller no (1) suddenly appearing after a bigger no (7) is happening in the same way. It doesn't really matter then that we rotated the array this way or that way. Hence we now know that the rotation will have no effect on result and thus in our approach in solving the problem. So the second property of rotation has no impact on our approach towards solving the problem.

Choose an approach (algorithm):

Now that we understand the problem we go ahead with how to choose an algorithm to go about solving it (if the word algorithm scares you just think of it as a recipe to a yummy food item- basically the "how" of doing it, but also the "when" and the "where"- like how you roast the seeds and when you put the sugar and where you heat it-microwave oven).

The algorithm will expect an input of a no of digits in ascending order, rotated until some point. So basically what we can do is start reading the input integers and check whether they are in ascending order. How do we do that? Just keep checking if the current no is smaller than the next no. The moment we find that the current no is greater than the next no, we've achieved our goal.

Code for it (make it pythonic):

def find_min_element(L):
    """This method finds the min element in a sorted list/array that has been
    rotated.
    """
    for i,element in enumerate(L):
        if (i+1<len(L)):#making sure index not out of range
            if L[i+1]<element:
                return L[i+1]
    return None

if __name__=="__main__":
    L=map(int, raw_input('Input noes(sorted list, rotated, separated by space): ').split())
    print "Input List:",L

    minval=find_min_element(L)
    if minval is None:
        print "Array is not rotated. No element found"
    else:
        print "Rotated array. Min element:%d"%minval
ps: check if there is a better way in python to access next element?

Test it:

import unittest
from minlist import *

class TestRotatedArray(unittest.TestCase):

  def test_sorted_input_rotn(self):
      self.assertEqual(find_min_element([1,2,3,4,0]), 0)

  def test_sorted_input_no_rotn(self):
      self.assertEqual(find_min_element([1,2,3,4]), None)

if __name__ == '__main__':
    unittest.main()
    
>>python unitestminlist.py
Ran 2 tests in 0.000s

OK