Search in Rotated Sorted Array - CA20

My Thinking and Approach

---

Introduction

In this problem, I was given a sorted array that is rotated at some unknown index and asked to find a target element.

The challenge is to do this in O(log n) time.

---

Problem Statement

• Given a rotated sorted array nums

• Given a target value

• Return index of target if found

• Otherwise return -1

• Conditions:

  • Array is sorted but rotated
  • All elements are unique
  • Time complexity must be O(log n)

---

My Initial Thought

At first, I considered:

• Using linear search

But this approach takes O(n) time and does not satisfy the requirement.

---

Key Observation

Even though the array is rotated:

• At least one half of the array is always sorted
• I can use this property to apply binary search

---

Optimized Approach

I decided to modify binary search.

Logic:

• Find mid element
• Check which half is sorted
• Decide where the target lies
• Move search accordingly

---

My Approach (Step-by-Step)

1. Initialize:

• left = 0
• right = n - 1

1. While left <= right:

• Find mid = (left + right) // 2
• If nums[mid] == target → return mid

1. Check sorted half:

• If left half is sorted:

  • If target lies in this range → search left
  • Else → search right

• Else right half is sorted:

  • If target lies in this range → search right
  • Else → search left

1. If not found → return -1

---

Code (Python)

Below is the implementation clearly separated inside a code block:

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

        while left <= right:
            mid = (left + right) // 2

            if nums[mid] == target:
                return mid

            if nums[left] <= nums[mid]:
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            else:
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1

        return -1

---

Example Walkthrough

Input:

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

Steps:

• mid = 3 → value = 7
• Left half sorted → target not in range → search right
• mid = 5 → value = 1
• Right half sorted → target not in range → search left
• mid = 4 → value = 0 → found

Output:

4

---

Complexity Analysis

Type	Complexity
Time Complexity	O(log n)
Space Complexity	O(1)

---

Key Takeaways

• Binary search can be modified for rotated arrays
• One half is always sorted
• Efficient search reduces time complexity

---

Conclusion

This problem helped me understand how to apply binary search in a rotated sorted array and still achieve optimal performance.

---