using System;

class Solution
{
    public static int ShiftedArrSearch(int[] shiftArr, int num)
    {
      if(shiftArr == null || shiftArr.Length == 0)
      {
        return -1;
      }

      return runModifiedBinarySearch(shiftArr, num, 0, shiftArr.Length - 1);
    }

  /// try to find half with ascending order
  private static int runModifiedBinarySearch(int[] numbers, int search, int start, int end)
  {
    if(start > end )
    {
      return -1;
    }

    int middle = start + (end - start)/ 2;
    bool found = numbers[middle] == search;

    if(found)
    {
      return middle;
    }

    var middleValue = numbers[middle];
    var startValue  = numbers[start];
    var endValue    = numbers[end];

    var firstHalfAscending  = startValue < middleValue; // [9, 12, 17, 2, 4, 5], 9 < 17
   //ar secondHalfAscending = middleValue    < endValue;
    // 53,90,2,3,4,5,6,8,9,10 -> 90
    // start = 0 , end = 9, middle = 4 , middleValue = 4,
    if(firstHalfAscending) // 53 < 4 false
    {
      var isInFirstHalfRange = search >= startValue && search < middleValue;
      if(isInFirstHalfRange)
      {
        return runModifiedBinarySearch(numbers, search, start, middle - 1);
      }
      else
      {
        return runModifiedBinarySearch(numbers, search, middle + 1, end);
      }
    }

      var isInSecondHalfRange = search > middleValue && search <= endValue; // [4, 10]
      if(isInSecondHalfRange)
      {
        return runModifiedBinarySearch(numbers, search, middle + 1, end);
      }
      else
      {
        return runModifiedBinarySearch(numbers, search, start, middle - 1); // 0, 3, [53, 90, 1, 2]
      }
  }

    static void Main(string[] args)
    {

    }
}

// 1, 2, 3, 4, 5
// 3, 4, 5, 1, 2 -> [3, 4, 5]  and second part [1, 2], k = 2
// special case k = 0
// given num, try to find index of num -> binary search -> O(logn)
// O(n) - brute force
// special modified binary search
// [9, 12, 17, 2, 4, 5]  -> 17 > 2 , call 2 is pivot position
// size = 6, middle 0 - 5 , 2,   17 , [9, 12, 17] -> ascending order -> [17, 2, 4, 5]  descending -> pivot
// 2 -> start value -> search -> binary search