Search in Rotated Sorted Array in DSA Python - Execution Trace

Concept Flow - Search in Rotated Sorted Array

Start: Define search range low=0, high=n-1

↓

Calculate mid = (low+high)//2

↓

Check if nums[mid

↓

Return mid

↓

Left half sorted

↓

Check if target in left

↓

Move high=mid-1

↓

Repeat until low > high

↓

Return -1 if not found

This flow shows how binary search adapts to a rotated sorted array by checking which half is sorted and narrowing the search range accordingly.

Execution Sample

DSA Python

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

This code searches for a target in a rotated sorted array using a modified binary search.

Execution Table

Step	Operation	low	high	mid	nums[mid]	Check	Action	Search Range	Result
1	Initialize	0	6	-	-	-	Set low=0, high=6	[0..6]	-
2	Calculate mid	0	6	3	7	nums[mid] == target? 7 == 0? No	Check which half sorted	[0..6]	-
3	Check left half sorted	0	6	3	7	nums[low] <= nums[mid]? 4 <= 7? Yes	Check if target in left half	[0..6]	-
4	Check target in left half	0	6	3	7	4 <= 0 < 7? No	Move low to mid+1=4	[4..6]	-
5	Calculate mid	4	6	5	1	nums[mid] == target? 1 == 0? No	Check which half sorted	[4..6]	-
6	Check left half sorted	4	6	5	1	nums[low] <= nums[mid]? 0 <= 1? Yes	Check if target in left half	[4..6]	-
7	Check target in left half	4	6	5	1	0 <= 0 < 1? Yes	Move high to mid-1=4	[4..4]	-
8	Calculate mid	4	4	4	0	nums[mid] == target? 0 == 0? Yes	Return mid=4	[4..4]	Found at index 4
9	End	-	-	-	-	-	-	-	-

💡 Target found at index 4, search ends.

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 5	After Step 7	After Step 8	Final
low	0	0	4	4	4	4	4
high	6	6	6	6	4	4	4
mid	-	3	3	5	5	4	4
nums[mid]	-	7	7	1	1	0	0

Key Moments - 3 Insights

Why do we check if the left half is sorted using nums[low] <= nums[mid]?

Because in a rotated sorted array, one half is always sorted. Checking nums[low] <= nums[mid] tells us if the left half is sorted, so we know where to search next (see execution_table step 3).

Why do we move low to mid+1 when the target is not in the sorted half?

If the target is not in the sorted half, it must be in the other half. So we adjust low or high to search the other half (see execution_table step 4).

Why does the loop stop when low > high?

Because low > high means the search range is empty and the target is not found (see execution_table step 9).

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the new value of low?

A 3

B 4

C 0

D 6

💡 Hint

Check the 'Action' and 'Search Range' columns at step 4 in execution_table.

At which step does the target get found?

A Step 5

B Step 7

C Step 8

D Step 9

💡 Hint

Look for 'Return mid' and 'Found at index' in the 'Result' column.

If the target was 5 instead of 0, what would happen at step 4?

A high would move to mid-1

B low would move to mid+1

C target found at mid

D loop ends immediately

💡 Hint

Check how the code moves low or high depending on target position relative to sorted half in execution_table step 4.

Concept Snapshot

Search in Rotated Sorted Array:
- Use binary search with low, high pointers
- Calculate mid = (low+high)//2
- Check if nums[mid] == target
- Determine which half is sorted (left or right)
- Narrow search to half containing target
- Repeat until found or range empty
- Return index or -1 if not found

Full Transcript

This concept shows how to search a target in a rotated sorted array using a modified binary search. We start with low and high pointers at the ends of the array. We calculate mid and check if nums[mid] equals the target. If not, we check which half of the array is sorted by comparing nums[low] and nums[mid]. Depending on which half is sorted and whether the target lies in that half, we adjust low or high to narrow the search range. We repeat this until we find the target or the search range becomes empty. The execution table traces each step with variable values and decisions. Key moments clarify why we check the sorted half and how we move pointers. The visual quiz tests understanding of pointer updates and termination conditions.

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