Search Rotated sorted array

Searching in a Rotated Sorted Array Using Binary Search

In many coding problems, you are given a sorted array that has been rotated at some unknown pivot. Your task is to find the index of a target element efficiently.

A rotated sorted array might look like this:

nums = [4, 5, 6, 7, 0, 1, 2]

This was originally sorted but then rotated. A normal binary search does not directly work here because the array is no longer completely sorted.

Why This Approach?

A brute-force approach would scan every element and take O(n) time.
However, even though the array is rotated, one important property still holds:

At least one half of the array (left or right) is always sorted.
This allows us to adapt binary search and still achieve O(log n) time complexity.

Code Overview
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        low, high = 0, len(nums) - 1

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

            if nums[mid] == target:
                return mid

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

        return -1

Step-by-Step Explanation
1. Initialize Search Space

low, high = 0, len(nums) - 1

We define the boundaries of the array.

2. Binary Search Loop

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

We repeatedly divide the search space in half.

3. Check if Target Found

if nums[mid] == target:
return mid

If the middle element matches the target, return its index immediately.

Key Logic: Identifying the Sorted Half

At every step, we determine which half of the array is sorted.

Case 1: Left Half is Sorted
if nums[low] <= nums[mid]:

This means the left portion from low to mid is sorted.

Now check if the target lies within this range:

if nums[low] <= target < nums[mid]:
high = mid - 1
else:
low = mid + 1
If the target is within the sorted left half, search there.
Otherwise, search in the right half.

If the left half is not sorted, then the right half must be sorted.

else:

Now check if the target lies in the right half:

if nums[mid] < target <= nums[high]:
low = mid + 1
else:
high = mid - 1
If the target is within the sorted right half, search there.
Otherwise, search in the left half.
Example Walkthrough

Consider:

nums = [4, 5, 6, 7, 0, 1, 2]
target = 0
First mid points to 7
Left half is sorted, but target is not in it
Move to the right half
Eventually find 0 at index 4