Search in Rotated Sorted Array

In this task, I worked on finding a target element in a rotated sorted array using an efficient approach.

A rotated sorted array is one that was originally sorted but then rotated at some pivot point.
For example: [4, 5, 6, 7, 0, 1, 2]

What I Did

I created a function search that:

• Takes an array nums and a target value
• Returns the index of the target if found
• Returns -1 if the target does not exist

How I Solved It

Instead of using a linear search , I used a modified binary search.

Approach

I used two pointers:

• low starting from index 0
• high starting from index n - 1

Then I repeatedly calculated the middle index mid.

Logic Behind It

At each step:

1. Check if Middle is Target

• If nums[mid] == target, return mid

2. Identify the Sorted Half

Case 1: Left Half is Sorted

• If nums[low] <= nums[mid]

• Check if target lies between low and mid:

  • YES → move high = mid - 1
  • NO → move low = mid + 1

Case 2: Right Half is Sorted

• Otherwise, the right half is sorted

• Check if target lies between mid and high:

  • YES → move low = mid + 1
  • NO → move high = mid - 1

Code

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

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

            if nums[mid] == target:
                return mid

            if nums[low] <= nums[mid]:
                if nums[low] <= target < nums[mid]:
                    high = mid - 1
                else:
                    low = mid + 1
            else:
                if nums[mid] < target <= nums[high]:
                    low = mid + 1
                else:
                    high = mid - 1

        return -1

How It Works

• Detects which side is properly sorted
• Narrows down the search space accordingly
• Repeats until it finds the target or exhausts the range

Time Complexity

• O(log n)

Example

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