using System;

//if lo >mid -> pivot is on the right
// if hi <mid -> pivot is on the left;

//Case 1 :- pivot on right  hi < mid -> and  lo <num <mid :- hi = mid-1;
//case 2 :- else of case 1 :- lo = mid +1

//case 3 :- pivot on left end :- lo > mid :- and mid < num < hi :- lo = mid+1
//case 4 :- else of case 1 :- hi= mid-1;

// [1,2] :- 2

// mid - a[0] -> 1

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

      int lo=0, hi= shiftArr.Length-1;

      while(lo<=hi)
      {
        int mid = lo + (hi-lo)/2;
        int middleValue = shiftArr[mid];
        int highValue = shiftArr[hi];

        if(middleValue == num)
          return mid;

        if(highValue < middleValue)  //case 1 and 2  ?
        {
          // left half ascending
          if(shiftArr[lo] <= num && middleValue > num)
            hi=mid-1;
          else
            lo= mid +1;

        }
        else
        {
          if(shiftArr[hi] >= num && middleValue < num)
            lo=mid+1;
          else
            hi=mid-1;
        }
      }

      return -1;
    }

    static void Main(string[] args)
    {
      int[] arr = new int[]{1,2};
      Console.WriteLine(ShiftedArrSearch(arr, 2));
    }
}