Search in Rotated Sorted Array in DSA C - Execution Trace

Concept Flow - Search in Rotated Sorted Array

Start with array and target

↓

Initialize low=0, high=n-1

↓

While low <= high

↓

Calculate mid = (low+high)/2

↓

Check if array[mid

↓

Return mid

↓

If left half sorted

↓

Target in left?

↓

high=mid-1

↓

Repeat loop

↓

If not found, return -1

This flow shows how binary search adapts to a rotated sorted array by checking sorted halves and narrowing search.

Execution Sample

DSA C

int search(int* nums, int n, int target) {
  int low = 0, high = n - 1;
  while (low <= high) {
    int mid = low + (high - low) / 2;
    if (nums[mid] == target) return mid;
    if (nums[low] <= nums[mid]) {
      if (target >= nums[low] && target < nums[mid]) high = mid - 1;
      else low = mid + 1;
    } else {
      if (target > nums[mid] && target <= nums[high]) low = mid + 1;
      else high = mid - 1;
    }
  }
  return -1;
}

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

Execution Table

Step	Operation	low	high	mid	nums[mid]	Check Sorted Half	Pointer Changes	Visual State
1	Initialize	0	6	-	-	-	-	[4,5,6,7,0,1,2]
2	Calculate mid	0	6	3	7	Left half sorted (4 to 7)	-	[4,5,6,7,0,1,2]
3	Check target=0 in left half?	0	6	3	7	Target not in left half	low=mid+1=4	[4,5,6,7,0,1,2]
4	Calculate mid	4	6	5	1	Right half sorted (0 to 2)	-	[4,5,6,7,0,1,2]
5	Check target=0 in right half?	4	6	5	1	Target in left half	high=mid-1=4	[4,5,6,7,0,1,2]
6	Calculate mid	4	4	4	0	Single element	-	[4,5,6,7,0,1,2]
7	nums[mid] == target?	4	4	4	0	Yes	-	[4,5,6,7,0,1,2]
8	Return index	-	-	4	0	-	-	[4,5,6,7,0,1,2]

💡 Target found at index 4, search ends.

Variable Tracker

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

Key Moments - 3 Insights

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

Because in a rotated 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 step 2 in execution_table).

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

If target is not in the sorted half, it must be in the other half. So we move low or high to narrow search to the unsorted half (see step 3 and 5).

Why does the loop stop when low > high?

Because low > high means the search space is empty and target is not found (not shown in this example as target is found).

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the value of low after pointer changes?

A 3

B 4

C 0

D 6

💡 Hint

Check the 'Pointer Changes' column at step 3 in execution_table.

At which step does the algorithm find the target?

A Step 7

B Step 6

C Step 4

D Step 8

💡 Hint

Look for 'nums[mid] == target?' with 'Yes' in execution_table.

If the target was 3 instead of 0, what would happen to the 'low' pointer after step 3?

A It would stay at 0

B It would move to 1

C It would move to 4

D It would move to 3

💡 Hint

Consider if target 3 is in left half sorted range at step 3.

Concept Snapshot

Search in Rotated Sorted Array:
- Use binary search with low, high pointers
- Find mid = (low+high)/2
- Check if left half (low to mid) is sorted
- If target in sorted half, move high or low accordingly
- Else search in other half
- Repeat until found or low > high
- 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 array ends. We calculate mid and check if nums[mid] equals target. If not, we check which half is sorted by comparing nums[low] and nums[mid]. If left half is sorted and target lies within it, we move high to mid-1 to search left half. Otherwise, we move low to mid+1 to search right half. If right half is sorted, we do the opposite. We repeat this until we find the target or low exceeds high, meaning target is not present. The execution table traces these steps with pointer changes and array states. Key moments clarify why we check sorted halves and how pointers move. The visual quiz tests understanding of pointer updates and target finding steps.

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 is not fully sorted, so normal binary search cannot be directly applied

B. The array contains duplicate elements

C. The array size is unknown

D. The array elements are all negative

Solution

1. Step 1: Understand sorted vs rotated sorted array

   A normal sorted array is fully sorted in ascending order, but a rotated sorted array is a sorted array shifted at some pivot point, breaking the full order.

2. Step 2: Impact on binary search

   Binary search requires a fully sorted array to decide which half to search next. In a rotated array, this condition breaks, so normal binary search cannot be directly applied.

3. Final Answer:

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

4. Quick Check:

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

Hint: Rotated array breaks order; normal binary search fails [OK]

Common Mistakes:

• Assuming array is fully sorted
• Ignoring the pivot point
• Thinking duplicates cause the main issue

2. Which of the following is the correct way to check if the middle element is in the left sorted portion of a rotated sorted array in C?

easy

A. if (arr[mid] > arr[end])

B. if (arr[mid] >= arr[start])

C. if (arr[mid] <= arr[start])

D. if (arr[mid] < arr[end])

Solution

1. Step 1: Understand left sorted portion condition

   If the middle element is greater than or equal to the start element, it means mid is in the left sorted portion because left side is sorted ascending.

2. Step 2: Translate condition to code

   The condition is written as if (arr[mid] >= arr[start]) in C to check this.

3. Final Answer:

   if (arr[mid] >= arr[start]) -> Option B

4. Quick Check:

   Mid >= start means left sorted [OK]

Hint: Check if mid >= start to find left sorted part [OK]

Common Mistakes:

• Using <= instead of > or >=
• Comparing mid with end incorrectly
• Confusing left and right sorted parts

3. What will be the output of the following C code snippet?

int arr[] = {6,7,8,1,2,3,4,5};
int n = 8;
int target = 3;
int start = 0, end = n - 1;
int mid;
while (start <= end) {
    mid = (start + end) / 2;
    if (arr[mid] == target) {
        printf("%d", mid);
        break;
    }
    if (arr[start] <= arr[mid]) {
        if (target >= arr[start] && target < arr[mid])
            end = mid - 1;
        else
            start = mid + 1;
    } else {
        if (target > arr[mid] && target <= arr[end])
            start = mid + 1;
        else
            end = mid - 1;
    }
}

medium

A. 6

B. 3

C. 2

D. 5

Solution

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

   Initial array: [6,7,8,1,2,3,4,5], target=3. Start=0, end=7. - mid=(0+7)/2=3, arr[3]=1, not target. - arr[start]=6 > arr[mid]=1, so right half is sorted. - target=3 > arr[mid]=1 and target <= arr[end]=5, so start=mid+1=4. - Now start=4, end=7. - mid=(4+7)/2=5, arr[5]=3 matches target.

2. Step 2: Output the index

   Index 5 is printed as the target is found at arr[5].

3. Final Answer:

   5 -> Option D

4. Quick Check:

   Target 3 found at index 5 [OK]

Hint: Trace mid and adjust start/end carefully [OK]

Common Mistakes:

• Not updating start/end correctly
• Confusing which half is sorted
• Wrong mid calculation

4. Identify the bug in the following C code snippet that searches for a target in a rotated sorted array:

int search(int arr[], int n, int target) {
    int start = 0, end = n - 1;
    while (start < end) {
        int mid = (start + end) / 2;
        if (arr[mid] == target) return mid;
        if (arr[start] <= arr[mid]) {
            if (target >= arr[start] && target < arr[mid])
                end = mid - 1;
            else
                start = mid + 1;
        } else {
            if (target > arr[mid] && target <= arr[end])
                start = mid + 1;
            else
                end = mid - 1;
        }
    }
    return -1;
}

medium

A. The target comparison should use > instead of >=

B. The mid calculation should be mid = start + (end - start) / 2

C. The loop condition should be start <= end instead of start < end

D. The function should return start instead of -1 when not found

Solution

1. Step 1: Analyze loop condition impact

   The loop uses while (start < end), which misses the case when start == end. This can skip checking the last element, causing incorrect -1 return even if target is present.

2. Step 2: Correct loop condition

   Changing to while (start <= end) ensures the last element is checked, preventing missed targets.

3. Final Answer:

   The loop condition should be start <= end instead of start < end -> Option C

4. Quick Check:

   Loop must include start == end to check all elements [OK]

Hint: Use start <= end to cover all elements [OK]

Common Mistakes:

• Ignoring last element check
• Thinking mid calculation causes bug
• Returning wrong index on failure

5. Given a rotated sorted array with possible duplicates, which modification is necessary to correctly search for a target element?

hard

A. Add extra checks to skip duplicates when arr[start] == arr[mid] == arr[end]

B. Use linear search instead of binary search

C. Ignore duplicates and apply normal rotated array search

D. Sort the array before searching

Solution

1. Step 1: Understand duplicates impact on rotated search

   Duplicates can cause ambiguity in deciding which half is sorted because arr[start], arr[mid], and arr[end] can be equal, breaking the binary search logic.

2. Step 2: Modify search to handle duplicates

   When arr[start] == arr[mid] == arr[end], increment start and decrement end to skip duplicates and continue search safely.

3. Step 3: Avoid linear search or sorting

   Linear search is inefficient; sorting changes array and is not allowed. Proper duplicate handling preserves binary search efficiency.

4. Final Answer:

   Add extra checks to skip duplicates when arr[start] == arr[mid] == arr[end] -> Option A

5. Quick Check:

   Skip duplicates when start=mid=end to continue search [OK]

Hint: Skip duplicates when start, mid, end equal [OK]

Common Mistakes:

• Ignoring duplicates cause wrong half detection
• Switching to linear search unnecessarily
• Sorting array before search