CareerCup

The code will take a binary search approach with few checks in between. Complexity = O(logn)

int FindPivotIndex(vector<int> arr)
{
	int size = arr.size();

	int first = 0, last = size - 1;
	while (first <= last)
	{
		if (arr[first] <= arr[last])
			return first;
		int mid = (first + last) / 2;

		if (arr[mid] < arr[first] && arr[mid] <= arr[last])
		{
			if (arr[mid - 1] > arr[mid])
				return mid;
			// pivot in first half
			last = mid - 1;
		}
		else if (arr[mid] >= arr[first] && arr[mid] > arr[last])
		{
			//pivot in second half
			first = mid + 1;
		}
	}	

	return -1;
}

def find_pivot(array):
    left = 0;
    right = len(array) - 1
    cur = (right + left) / 2

    while left < cur < right:
        cur = (right + left) / 2

        if array[cur] <  array[right]:
            left = cur
        elif array[left] < array[cur]:
            right = cur


    return cur