<jupyter_start><jupyter_text>Unknown RotationsA sorted array of integers was rotated an unknown number of times...given such an array, find the index of the element in the array in faster than linear time. If the element doesn't exist in the array, return null.Example: given [13,18,25,2,8,10] and the element 8, return 4 (index of 8 in the array). Thoughts: You can assume that all of the integers in the array are unique.<jupyter_code># The brute force way of doing this does it in linear time.

def unknown_rotations(arr, element): 
    for i in range(len(arr)): 
        if element == arr[i]: 
            return i
test_arr = [13,18,25,2,8,10]
test_ele = 8
unknown_rotations(test_arr, test_ele)
test_ele2 = 18
unknown_rotations(test_arr, test_ele2)
# The question though... the hard part is in doing it faster than linear time!
# if the array was just sorted, then we could use a binary search
# because the array was sorted and then rotated --> you need to be a little more clever


# find the rotation point using binary search
def fast_rotations(lst, num): 
    
    # find the breaking point in the shifted array
    i = len(lst) // 2
    dist = i // 2
    
    while True: 
        if lst[0] > lst[i] and lst[i-1] > lst[i]: 
            break
        elif dist == 0 : 
            break
        elif lst[0] <= lst[i]: 
            i = i + dist
        elif lst[i-1] <= lst[i]: 
            i = i - dist
        else: 
            break 
        dist = dist // 2 
        
        
    # i gives us the index position of the bottom (low) 
    # now we run binary search, but wrap around the rotation
    
    low = i
    high = i - 1
    dist = len(lst) // 2 
    
    while True: 
        if dist == 0: 
            return None
        
        guess_ind = (low + dist) % len(lst) 
        guess = lst[guess_ind] 
        if guess == num: 
            return guess_ind
        
        
        if guess < num: 
            low = (low + dist) % len(lst) 
        if guess > num: 
            high = (len(lst) + high - dist) % len(lst) 
            
        dist = dist // 2 
        
    
fast_rotations(test_arr, test_ele)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.08556891766882516, 'fraction_numerical': 0.018501387604070305, 'mean_word_length': 1.9308943089430894, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '18592', 'license': 'MIT', 'n_tokens_mistral': 702, 'n_tokens_neox': 648, 'n_words': 265, 'path': 'Daily/Unknown Rotations.ipynb', 'repo_name': 'jasonyum/python_go', 'size': '2162'}