Rotation point

RotationPoint

// https://www.interviewcake.com/question/find-rotation-point?utm_source=weekly_email

using System;

namespace RotationPoint
{
    public class Program
    {
        public static void Main(string[] args)
        {
            // string[] input = new string[]{"pear", "ultra", "xeno", "apple", "bat"};
            // string[] input = new string[]{"pear", "ultra", "xeno"};
            // string[] input = new string[]{"pear", "ultra", "xeno", "bat"};
            string[] input = new string[]{"pear", "umbrella", "cherry", "guava"};
            // string[] input = new string[]{"apple", "bat", "cat"};
            // string[] input = new string[]{"k","v","a","b","c","d","e","g","i"};
            // string[] input = new string[]{"k"};
                           
            var rotationPoint = findRotation(input);
            if (rotationPoint == -1) {
                Console.WriteLine("Could not find rotation point");
            } else {
                Console.WriteLine("Rotation point is {0} ", input[rotationPoint]);   
            }
        }
        
        // Time complexity: O(log(n))
        private static int findRotation(string[] words) {
            if (words.Length < 2) {
                return -1;
            }
             
            int low = 0;
            int high = words.Length - 1;
            int mid = 0;
            
            while (low < high) {
                mid = (low + high) / 2;
                
                if (words[low].CompareTo(words[mid]) < 0) {
                    low = mid;
                } else {
                    high = mid;
                }
                
                if (low + 1 == high) {
                    // This means the input is not rotated
                    if (words[low].CompareTo(words[high]) < 0) {
                        return 0;
                    }
                    
                    return high;
                }
            }
            
            return -1;
        }
    }
}