Search in Rotated Sorted Array in DSA Python

Mental Model

We look for a number in a list that was sorted but then turned around at some point. We use a smart search that checks which part is still sorted to find the number quickly.

Analogy: Imagine a clock face with numbers in order but someone rotated it. To find a number, you check which half of the clock is still in order and decide where to look next.

Original sorted array:
[1] -> [2] -> [3] -> [4] -> [5] -> [6] -> [7] -> null

Rotated array example:
[4] -> [5] -> [6] -> [7] -> [1] -> [2] -> [3] -> null

Pointers:
start ↑                      end ↑

Dry Run Walkthrough

Input: array: [4,5,6,7,0,1,2], target: 0

Goal: Find the index of target 0 in the rotated sorted array

Step 1: Set start=0, end=6, find mid=(0+6)//2=3

[4] -> [5] -> [6] -> [7]↑mid -> [0] -> [1] -> [2]
start=0, mid=3, end=6

Why: We start searching in the whole array by checking the middle element

Step 2: Check if target=0 equals mid element=7 (no), then check which half is sorted

[4] -> [5] -> [6] -> [7]↑mid -> [0] -> [1] -> [2]
start=0, mid=3, end=6

Why: We need to know which side is sorted to decide where to search next

Step 3: Left half [4..7] is sorted because 4 <= 7, check if target=0 is in [4..7] (no)

[4] -> [5] -> [6] -> [7]↑mid -> [0] -> [1] -> [2]
start=0, mid=3, end=6

Why: Target is not in the sorted left half, so search right half

Step 4: Move start to mid+1=4 to search right half

[4] -> [5] -> [6] -> [7] -> [0]↑start -> [1] -> [2]
start=4, end=6

Why: We narrow search to the right half where target might be

Step 5: Calculate mid=(4+6)//2=5, mid element=1

[4] -> [5] -> [6] -> [7] -> [0] -> [1]↑mid -> [2]
start=4, mid=5, end=6

Why: Check middle of new search range

Step 6: Check if target=0 equals mid element=1 (no), check which half is sorted

[4] -> [5] -> [6] -> [7] -> [0] -> [1]↑mid -> [2]
start=4, mid=5, end=6

Why: Determine sorted half to decide next search

Step 7: Left half [0..1] is sorted because 0 <= 1, check if target=0 is in [0..1] (yes)

[4] -> [5] -> [6] -> [7] -> [0] -> [1]↑mid -> [2]
start=4, mid=5, end=6

Why: Target is in sorted left half, so search left half

Step 8: Move end to mid-1=4 to search left half

[4] -> [5] -> [6] -> [7] -> [0]↑end -> [1] -> [2]
start=4, end=4

Why: Narrow search to left half where target is

Step 9: Calculate mid=(4+4)//2=4, mid element=0

[4] -> [5] -> [6] -> [7] -> [0]↑mid -> [1] -> [2]
start=4, mid=4, end=4

Why: Check the only element left

Step 10: Found target=0 at index 4

[4] -> [5] -> [6] -> [7] -> [0]↑mid -> [1] -> [2]
start=4, mid=4, end=4

Why: Target found, search ends

Result:

[4] -> [5] -> [6] -> [7] -> [0]↑mid -> [1] -> [2]
Target 0 found at index 4

Annotated Code

DSA Python

class Solution:
    def search(self, nums: list[int], target: int) -> int:
        start, end = 0, len(nums) - 1
        while start <= end:
            mid = (start + end) // 2
            if nums[mid] == target:
                return mid
            # Check if left half is sorted
            if nums[start] <= nums[mid]:
                # Check if target is in left half
                if nums[start] <= target < nums[mid]:
                    end = mid - 1
                else:
                    start = mid + 1
            else:
                # Right half is sorted
                if nums[mid] < target <= nums[end]:
                    start = mid + 1
                else:
                    end = mid - 1
        return -1

# Driver code
sol = Solution()
nums = [4,5,6,7,0,1,2]
target = 0
index = sol.search(nums, target)
if index != -1:
    print(f"Target {target} found at index {index}")
else:
    print(f"Target {target} not found")

while start <= end:

continue searching while range is valid

mid = (start + end) // 2

find middle index of current search range

if nums[mid] == target:

check if middle element is the target

if nums[start] <= nums[mid]:

check if left half is sorted

if nums[start] <= target < nums[mid]:

check if target lies in sorted left half

end = mid - 1

narrow search to left half

else: start = mid + 1

search right half if target not in left half

else:

right half is sorted

if nums[mid] < target <= nums[end]:

check if target lies in sorted right half

start = mid + 1

narrow search to right half

else: end = mid - 1

search left half if target not in right half

Output

Target 0 found at index 4

Complexity Analysis

Time: O(log n) because each step halves the search range by checking sorted halves

Space: O(1) because only a few variables are used regardless of input size

vs Alternative: Naive linear search is O(n) because it checks each element; this method is faster by using binary search logic on rotated arrays

Edge Cases

empty array

returns -1 immediately because start > end

DSA Python

while start <= end:

array with one element equal to target

returns index 0 immediately

DSA Python

if nums[mid] == target:

array with one element not equal to target

returns -1 after one check

DSA Python

while start <= end:

target not in array

returns -1 after search exhausts range

DSA Python

return -1

When to Use This Pattern

When you see a sorted array that might be rotated and need to find a target quickly, use this pattern to apply modified binary search by checking which half is sorted.

Common Mistakes

Mistake: Not checking which half is sorted before deciding where to search next
Fix: Always compare nums[start] and nums[mid] to identify the sorted half before moving pointers

Mistake: Using <= or < incorrectly causing infinite loops or missing target
Fix: Use consistent comparison operators to correctly include or exclude mid and boundary elements

Summary

Finds a target in a rotated sorted array using a modified binary search.

Use when the array is sorted but rotated and you want fast search.

The key is to identify which half is sorted to decide where to search next.

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