Question: Find an Item in a Sorted Array with Shifted Elements

Solution: Binary Search! We can split the array in 2 halves and do a recursive search in one of the halves until we find the number we are looking for ( or not, if its not in the array ). This approach has a running time of O(log n)
// myArray is the input array
// startIndex and endIndex are the indexes in the
// array where the binary search starts and ends
// The method returns the index of the searchVal
// if found in the array, else it returns -1

int BinarySearch(int[] myArray, int startIndex, int endIndex, int searchVal);


// this method will return the index of the searchVal
// if found, else it return -1
int SearchElement(int[] myArray, int shift, int searchVal)
{
// to take care of scenarios where the shift is more
// than the length of the array
shift = shift % myArray.Length;

// -ve shift can be seen as positive shift equal to
// the length of the array - ( -ve shift)
if (shift < 0)
shift = myArray.Length + shift;

if(myArray[shift] <= searchVal &&
myArray[myArray.Length - 1] >= searchVal)
{
return BinarySearch(myArray, shift, myArray.Length - 1, searchVal);
}
else if(myArray[0] <= searchVal &&
myArray[shift - 1] >= searchVal)
{
return BinarySearch(myArray, 0, shift-1, searchVal);
}
return -1;
}