Solution: Search in a Rotated Array

using System;
class Program
{
    /// <summary>
    /// Method to search for a key in an array.
    /// </summary>
    /// <param name="arr">An array of integers.</param>
    /// <param name="n">The size of the array.</param>
    /// <param name="key">The key to be searched in the array.</param>
    public static int PivotedBinarySearch(int[] arr, int n, int key)
    {
        int pivot = FindPivotPoint(arr, 0, n - 1);
        // If the array is not rotated
        if (pivot == -1)
        {
            return BinarySearch(arr, 0, n - 1, key);
        }
        // If the array is rotated then find the elements in left and right subarrays
        if (arr[pivot] == key)
        {
            return pivot;
        }
        if (arr[0] <= key)
        {
            return BinarySearch(arr, 0, pivot - 1, key);
        }
        return BinarySearch(arr, pivot + 1, n - 1, key);
    }
    /// <summary>
    /// Method to pivot in the array.
    /// </summary>
    /// <param name="arr">An array of integers.</param>
    /// <param name="low">Lowest index of the array.</param>
    /// <param name="high">Highest index of the array.</param>
    static int FindPivotPoint(int[] arr, int low, int high)
    {
        // Base cases
        if (high < low)
        {
            return -1;
        }
        if (high == low)
        {
            return low;
        }
        int mid = (low + high) / 2;
        if (mid < high && arr[mid] > arr[mid + 1])
        {
            return mid;
        }
        if (mid > low && arr[mid] < arr[mid - 1])
        {
            return mid - 1;
        }
        if (arr[low] >= arr[mid])
        {
            return FindPivotPoint(arr, low, mid - 1);
        }
        return FindPivotPoint(arr, mid + 1, high);
    }
    /// <summary>
    /// Binary Search method
    /// </summary>
    /// <param name="arr">An array of integers.</param>
    /// <param name="low">Lowest index of the array.</param>
    /// <param name="high">Highest index of the array.</param>
    /// <param name="key">A key to be searched in the array.</param>
    public static int BinarySearch(int[] arr, int low, int high, int key)
    {
        if (high < low)
        {
            return -1;
        }
        int mid = (low + high) / 2;
        if (key == arr[mid])
        {
            return mid;
        }
        if (key > arr[mid])
        {
            return BinarySearch(arr, mid + 1, high, key);
        }
        return BinarySearch(arr, low, mid - 1, key);
    }
    public static void Main(string[] args)
    {
        int[] arr = { 6, 7, 8, 9, 10, 0, 1, 2, 3 };
        int key = 0;
        int n = arr.Length;
        int index = PivotedBinarySearch(arr, n, key);
        if (index != -1)
        {
            Console.WriteLine("Index of the element is: " + index);
        }
        else
        {
            Console.WriteLine("Element not found");
        }
    }
}