A rotated-sorted list is formed by sorting a list into non-decreasing order, dividing it into two sub-lists, and swapping the order of the sub-lists. Using list slice notation, if S is a sorted list, and i is some seam index, then S[i:] + S[:i] is a rotated-sorted list.

For example, the list [3, 1, 2, 4, 5] could be rotated-sorted into [4, 5, 1, 2, 3] , [5, 1, 2, 3, 4] , or even [1, 2, 3, 4, 5]

Design a decrease-by-half algorithm that solves the problem; describe your algorithm with clear pseudocode; and prove the time efficiency class of your algorithm.

def search(L, q):

search in a rotated-sorted list input: a rotated-sorted list L, and query value q output: the index i such that L[i]==q, or None if no such i exists Hint: An optimal algorithm for this problem has time complexity O(log n)