Search in Rotated Sorted Array in DSA Python - Build from Scratch

Search in Rotated Sorted Array

📖 Scenario: You have a list of numbers that was originally sorted but then rotated at some unknown point. For example, the list [4,5,6,7,0,1,2] was rotated after the number 7. You want to find if a specific number exists in this rotated list.

🎯 Goal: Build a program that searches for a target number in a rotated sorted array and returns its index if found, or -1 if not found.

📋 What You'll Learn

Create a list called nums with the exact values [4,5,6,7,0,1,2]

Create a variable called target and set it to 0

Write a function called search_rotated_array(nums, target) that returns the index of target in nums or -1 if not found

Use a binary search approach adapted for rotated sorted arrays inside the function

Print the result of calling search_rotated_array(nums, target)

💡 Why This Matters

🌍 Real World

Rotated sorted arrays appear in systems where data is cyclically shifted, such as in circular buffers or rotated logs.

💼 Career

Understanding how to efficiently search in rotated sorted arrays is useful for software engineers working on performance-critical applications and system design.

1

Create the rotated sorted array

Create a list called nums with these exact values: [4,5,6,7,0,1,2]

DSA Python

# Create the list nums with the rotated sorted values
# Your code here

Hint

Use square brackets to create the list and separate numbers with commas.

2

Set the target number to search

Create a variable called target and set it to 0

DSA Python

nums = [4,5,6,7,0,1,2]
# Create the variable target and set it to 0
# Your code here

Hint

Use the equals sign to assign the value 0 to the variable target.

3

Write the search function for rotated sorted array

Write a function called search_rotated_array(nums, target) that uses binary search to find the index of target in nums. Return the index if found, otherwise return -1. Use variables left, right, and mid inside the function.

DSA Python

nums = [4,5,6,7,0,1,2]
target = 0
# Define the function search_rotated_array(nums, target) below
# Your code here

Hint

Use a while loop with left and right pointers. Check if the middle element is the target. Decide which half to search next based on sorted halves.

4

Print the search result

Print the result of calling search_rotated_array(nums, target)

DSA Python

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

def search_rotated_array(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

# Print the index of target in nums
# Your code here

Hint

Use the print function to show the result of the search function call.

Practice

1. What is the main challenge when searching for an element in a rotated sorted array compared to a normal sorted array?

easy

A. The array elements are all negative numbers.

B. The array contains duplicate elements which confuse the search.

C. The array is not fully sorted, so normal binary search cannot be directly applied.

D. The array size is unknown, so we cannot set boundaries.

Solution

1. Step 1: Understand normal binary search

   Binary search works efficiently on fully sorted arrays by dividing the search space in half each time.

2. Step 2: Identify the challenge with rotated arrays

   In a rotated sorted array, the array is sorted but rotated at some pivot, so it is not fully sorted in one direction, making normal binary search invalid without adjustments.

3. Final Answer:

   The array is not fully sorted, so normal binary search cannot be directly applied. -> Option C

4. Quick Check:

   Rotated array breaks full sorting = normal binary search fails [OK]

Hint: Rotated means partial sorting, normal binary search fails [OK]

Common Mistakes:

• Assuming array is fully sorted
• Ignoring the rotation pivot
• Thinking duplicates cause the main problem

2. Which of the following is the correct syntax to start a binary search on a rotated sorted array named arr with target in Python?

easy

A. left, right = 1, len(arr) - 1

B. left, right = 1, len(arr)

C. left, right = 0, len(arr)

D. left, right = 0, len(arr) - 1

Solution

1. Step 1: Understand array indexing in Python

   Python arrays are zero-indexed, so the first element is at index 0 and the last at len(arr) - 1.

2. Step 2: Set search boundaries correctly

   To search the entire array, left should start at 0 and right at len(arr) - 1.

3. Final Answer:

   left, right = 0, len(arr) - 1 -> Option D

4. Quick Check:

   Zero-based indexing means last index is length minus one [OK]

Hint: Start left at 0 and right at length minus one [OK]

Common Mistakes:

• Starting left at 1 instead of 0
• Setting right to length instead of length - 1
• Confusing inclusive and exclusive ranges

3. What will be the output of the following Python code?

def search_rotated(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        if arr[left] <= arr[mid]:
            if arr[left] <= target < arr[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:
            if arr[mid] < target <= arr[right]:
                left = mid + 1
            else:
                right = mid - 1
    return -1

print(search_rotated([4,5,6,7,0,1,2], 0))

medium

A. -1

B. 4

C. 0

D. 6

Solution

1. Step 1: Trace the binary search on rotated array

   Array: [4,5,6,7,0,1,2], target: 0. Initial left=0, right=6, mid=3 (value 7). Since arr[left] <= arr[mid], left half is sorted. Target 0 is not in [4..7], so move left to mid+1=4.

2. Step 2: Continue search in right half

   Now left=4, right=6, mid=5 (value 1). arr[left] <= arr[mid], left half sorted. Target 0 is less than arr[mid], so right=mid-1=4. Next mid=4 (value 0), matches target, return 4.

3. Final Answer:

   4 -> Option B

4. Quick Check:

   Target 0 found at index 4 [OK]

Hint: Check which half is sorted, then narrow search [OK]

Common Mistakes:

• Not updating left/right correctly
• Confusing comparison operators
• Returning wrong index or -1 incorrectly

4. Identify the bug in the following code snippet for searching in a rotated sorted array:

def search(arr, target):
    left, right = 0, len(arr) - 1
    while left < right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        if arr[left] <= arr[mid]:
            if arr[left] <= target < arr[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:
            if arr[mid] < target <= arr[right]:
                left = mid + 1
            else:
                right = mid - 1
    return -1

medium

A. The loop condition should be while left <= right, not while left < right.

B. The mid calculation is incorrect; it should be mid = (left + right + 1) // 2.

C. The target comparison should use <= instead of < in all conditions.

D. The function should return left instead of -1 at the end.

Solution

1. Step 1: Analyze loop condition

   The loop uses while left < right, which stops when left == right, possibly missing the last element check.

2. Step 2: Correct loop condition for full search

   Using while left <= right ensures the search includes the last element, preventing missing the target at the boundary.

3. Final Answer:

   The loop condition should be while left <= right, not while left < right. -> Option A

4. Quick Check:

   Include last element by using <= in loop condition [OK]

Hint: Use <= in loop to check all elements including boundaries [OK]

Common Mistakes:

• Using < instead of <= in loop
• Miscomputing mid index
• Returning wrong value when not found

5. Given a rotated sorted array arr = [30, 40, 50, 10, 20], what is the index of the target 10 using an efficient search algorithm?

hard

A. 3

B. 2

C. 4

D. -1

Solution

1. Step 1: Identify the rotation and search boundaries

   Array: [30, 40, 50, 10, 20], target: 10. left=0, right=4, mid=2 (value 50). Left half is sorted (30 to 50).

2. Step 2: Decide which half to search

   Target 10 is not in left sorted half (30 to 50), so search right half: left=mid+1=3, right=4. mid=3 (value 10), matches target.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Target 10 found at index 3 [OK]

Hint: Check sorted half, then narrow search to find target [OK]

Common Mistakes:

• Assuming array is fully sorted
• Not updating left/right correctly
• Returning wrong index or -1 incorrectly