interview-questions/search-and-sort/search_in_rotated.py

# Search in a rotated sorted list, require time complexity O(logn)

import pytest

def test_search_in_rotated():
    case1 = [5,7,0,3,4]
    assert search_in_rotated(case1, 7) == 1
    assert search_in_rotated(case1, 6) == -1
    assert search_in_rotated(case1, 5) == 0

def search_in_rotated(l, target):
    left = 0
    right = len(l) - 1
    while right > left:
        m = (right - left) // 2
        if l[m] == target:
            return m
        if l[right] == target:
            return right
        if l[left] == target:
            return left
        # right portion is sorted
        if l[m] < l[right] and l[m] < l[left]:
            if target < l[right] and target > l[m]:
                left = m + 1
            else:
                right = m - 1
        # left portion is sorted
        elif l[m] > l[right] and l[m] > l[left]:
            if target > l[left] and target < l[m]:
                right = m - 1
            else:
                left = m + 1
        # list is sorted
        else:
            if target > l[m]:
                left = m + 1
            else:
                right = m - 1
    return -1