Повернутый массив: начнем с простого

Как перейти с [1, 2, 3, 4, 5, 6, 7, 8, 9] на [5, 6, 7, 8, 9, 1, 2, 3, 4]? Вызовите следующую функцию четыре раза.

"""
rotate once
"""
def rotate_array(arr):
    temp = arr[0]
    for i in range(1, len(arr)):
        arr[i - 1] = arr[i]
    arr[i] = temp
    return arr

Мы знаем, что бинарный поиск предпочтительнее, если массив отсортирован. Но что, если массив отсортирован и повернут? Можем ли мы по-прежнему выполнять бинарный поиск или разработать метод со сложностью O(logn)?

"""
A little bit subtle.
Note that for a rotated array, if cut in middle, there must be one segment that is sorted.
Using the sorted segment, we could compare the target and see if it's there, and then to decide to approach to the sorted
segment or the un-sorted segment.
Hard if not seen before.
"""
def binary_search_rotated(arr, low, high, target):
    while low <= high:
        mid = (low + high)/2
        print(mid)
        if arr[mid] == target:
            return mid
        if arr[low] < arr[mid - 1]:# sorted
            if arr[low] < target and arr[mid - 1] > target:
                binary_search_rotated(arr, low, mid - 1, target)
            else:
                binary_search_rotated(arr, mid + 1, high, target)
        else:
            if arr[mid + 1] < target and arr[high] > target:
                binary_search_rotated(arr, mid + 1, high, target)
            else:
                binary_search_rotated(arr, low, mid - 1, target)            
    return -1
print(rotate_array(a))
print(rotate_array(a))
binary_search(a, 0, len(a), 4)