Search in Rotated Sorted Array

Hi everyone!
Today I solved a really interesting problem where a sorted array is rotated, and we still need to search efficiently. This problem helped me understand how powerful binary search can be.

Problem
Given a sorted array that is rotated at some unknown index, find the index of a target element.
If not found, return -1.

Example:
Input: [4,5,6,7,0,1,2], target = 0

Output: 4

My Approach
At first, I thought normal binary search would work, but rotation breaks the sorted order.
Then I noticed:

At least one half of the array is always sorted
So I used a modified binary search.

Logic
Find mid element
Check which half is sorted:
If left half is sorted:
Check if target lies in it
Else right half is sorted:
Check if target lies there
Narrow down the search accordingly

Code (Python)
class Solution:
def search(self, nums, target):
l, r = 0, len(nums) - 1

    while l <= r:
        mid = (l + r) // 2

        if nums[mid] == target:
            return mid

        if nums[l] <= nums[mid]:
            if nums[l] <= target < nums[mid]:
                r = mid - 1
            else:
                l = mid + 1
        else:
            if nums[mid] < target <= nums[r]:
                l = mid + 1
            else:
                r = mid - 1

    return -1

Time & Space Complexity
Time: O(log n)
Space: O(1)

Key Insight
Even in a rotated array, one side is always sorted, and that helps us apply binary search.

What I Learned
Binary search can be modified for tricky cases*
Observing patterns is very important
This is a common interview problem

Thanks for reading!
Feel free to share your thoughts or different approaches.