Modified binary search - shift array search, the array shift unknown elements to the left. Given a number, try to find index of the element in the array with the given value.

ShiftArraySearch_binarySearch.cs

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 

Nov. 23, 2017
The code cannot pass Leetcode 33 online judge, the line 35 should include the case - the left half only has one element in the array, in other words, start == middle.
var firstHalfAscending = startValue < middleValue;