Big O Practice: Search Rotated Sorted

def search_rotated(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        if arr[lo] <= arr[mid]:
            if arr[lo] <= target < arr[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:
            if arr[mid] < target <= arr[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

Variables

• n - length of the rotated sorted array

Explanation

Even with the rotation, each iteration eliminates half the search space - **O(log n)** time, **O(1)** space. The branching is more involved but the halving is preserved.

More Big O practice problems · Today's daily problem