Interview Question for Software Development Engineer at Microsoft:

Required NOT using recursion but iteration. Hate that... But the final answer is 'short and elegant'

This is a variation from Binary Search, the key is to find the conditions when to move to left and when to stop, this is how I implemented. Any comments are welcome.

public int FindRotatedIndex(int[] array)
        {
            if (array == null)
                return -1;

            if (array.Length == 1)
                return 0;

            int l = 0; int u = array.Length - 1; int m;

            while (u - l != 1)
            {
                m = (u + l) / 2;
                if (MoveToLeft(array,l, m, u))
                   u = m;
                else
                   l = m;
            }

            return array[l] > array[u] ? u : l;
        }

        private bool MoveToLeft(int[] array, int l, int m, int u)
        {
            // cover this condition ex 3 1 2, ex 9 1 2 3 4 5 6, determine to move to the left,
            // the last part of condition is to prevent cases like ex 3 2 1 for moving to left
            bool lowerGreaterThanMidAndUpper = (array[l] > array[m] && array[l] > array[u] && array[u] > array[m]);
            // to cover conditions where array is not rotated 1 2 3
            bool lowerLessThanMidAndUpper = (array[l] < array[m] && array[l] < array[u]);

            return lowerGreaterThanMidAndUpper || lowerLessThanMidAndUpper;
        }