Search in Rotated Sorted Array

When I first saw this problem, it looked like a normal binary search. But then I noticed something tricky — the array is rotated. That means it’s not fully sorted anymore, but still has some structure we can use.

What I Realized
Even though the array is rotated, at least one half of the array is always sorted.That’s the key idea that makes this problem solvable in O(log n).
We are given:

A sorted array (ascending)
It is rotated at some unknown point
We need to find the index of a target value

If the target doesn’t exist → return -1
Example
Original: [0,1,2,4,5,6,7]
Rotated : [4,5,6,7,0,1,2]

Now if target = 0, answer = 4

My Approach

I used Binary Search, but with a twist:
Step 1:
Find middle element
Step 2:
Check which side is sorted:
If nums[low] <= nums[mid] → left side is sorted
Else → right side is sorted
Step 3:
Check if target lies in the sorted half:
If yes → search there
Else → search in the other half

Algorithm

   def search(self, nums, target):
        low, high = 0, len(nums) - 1

        while low <= high:
            mid = (low + high) // 2

            if nums[mid] == target:
                return mid

            # Left half is sorted
            if nums[low] <= nums[mid]:
                if nums[low] <= target < nums[mid]:
                    high = mid - 1
                else:
                    low = mid + 1

            # Right half is sorted
            else:
                if nums[mid] < target <= nums[high]:
                    low = mid + 1
                else:
                    high = mid - 1

        return -1