Search in Rotated Sorted Array Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. i.e., 0,1,2,4,5,6,7 might become 4,5,6,7,0,1,2. You are given a target value to search. If found in the array return its index, otherwise return 1. Your algorithm's runtime complexity must be in the order of Olog n.  Explanation algorithm: In classic binary search, we compare val with the midpoint to figure out if val belongs on the low or the high side. The complication here is that the array is rotated and may have an inflection point. Consider, for example: Array1: 10, 15, 20, 0, 5 Array2: 50, 5, 20, 30, 40 Note that both arrays have a midpoint of 20, but 5 appears on the left side of one and on the right side of the other. Therefore, comparing val with the midpoint is insufficient. However, if we look a bit deeper, we can see that one half of the array must be ordered normallyincreasing order. We can therefore look at the normally ordered half to determine whether we should search the low or hight side. For example, if we are searching for 5 in Array1, we can look at the left element 10 and middle element 20. Since 10  20, the left half must be ordered normally. And, since 5 is not between those, we know that we must search the right half In array2, we can see that since 50  20, the right half must be ordered normally. We turn to the middle 20, and right 40 element to check if 5 would fall between them. The value 5 would not Therefore, we search the left half. There are 2 possible solution: iterative and recursion. Recursion helps you understand better the above algorithm explanation Finds the index of the given value in an array that has been sorted in ascending order and then rotated at some unknown pivot. Recursion technique Finds the index of the given value in an array that has been sorted in ascending order and then rotated at some unknown pivot.
def search_rotate(array, val):
    """
    Finds the index of the given value in an array that has been sorted in
    ascending order and then rotated at some unknown pivot.
    """
    low, high = 0, len(array) - 1
    while low <= high:
        mid = (low + high) // 2
        if val == array[mid]:
            return mid

        if array[low] <= array[mid]:
            if array[low] <= val <= array[mid]:
                high = mid - 1
            else:
                low = mid + 1
        else:
            if array[mid] <= val <= array[high]:
                low = mid + 1
            else:
                high = mid - 1

    return -1

# Recursion technique
def search_rotate_recur(array, low, high, val):
    """
    Finds the index of the given value in an array that has been sorted in
    ascending order and then rotated at some unknown pivot.
    """
    if low >= high:
        return -1
    mid = (low + high) // 2
    if val == array[mid]:       # found element
        return mid
    if array[low] <= array[mid]:
        if array[low] <= val <= array[mid]:
            return search_rotate_recur(array, low, mid - 1, val)    # Search left
        return search_rotate_recur(array, mid + 1, high, val)   # Search right
    if array[mid] <= val <= array[high]:
        return search_rotate_recur(array, mid + 1, high, val)   # Search right
    return search_rotate_recur(array, low, mid - 1, val)    # Search left
