Search in Rotated Sorted Array in DSA C

Mental Model

We find a number in a sorted list that has been turned around at some point. We use a smart search that checks which part is still sorted to decide where to look next.

Analogy: Imagine a clock face cut and rotated so the numbers are not in usual order. To find a number, you check which half of the clock still has numbers 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
↑ start

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 low=0, high=6, mid=(0+6)/2=3, check value at mid=7

[4] -> [5] -> [6] -> [7] -> [0] -> [1] -> [2]
 indices: 0    1    2    3    4    5    6
 low=0, mid=3, high=6

Why: Start searching in the whole array, mid helps split the search

Step 2: Check if left half [4..7] is sorted: yes (4 <= 7), check if target 0 is in [4..7]: no

[4] -> [5] -> [6] -> [7] -> [0] -> [1] -> [2]
 low=0, mid=3, high=6

Why: Since left half is sorted but target is not in this range, search right half

Step 3: Set low=mid+1=4, high=6, mid=(4+6)/2=5, check value at mid=1

[4] -> [5] -> [6] -> [7] -> [0] -> [1] -> [2]
 low=4, mid=5, high=6

Why: Focus search on right half where target might be

Step 4: Check if left half [0..1] is sorted: yes (0 <= 1), check if target 0 is in [0..1]: yes

[4] -> [5] -> [6] -> [7] -> [0] -> [1] -> [2]
 low=4, mid=5, high=6

Why: Target is in this sorted half, so search here

Step 5: Set high=mid-1=4, low=4, mid=(4+4)/2=4, check value at mid=0

[4] -> [5] -> [6] -> [7] -> [0] -> [1] -> [2]
 low=4, mid=4, high=4

Why: Narrow down to left half to find exact target

Step 6: Value at mid=0 equals target, return index 4

[4] -> [5] -> [6] -> [7] -> [0] -> [1] -> [2]
 target found at index 4

Why: Found the target, stop searching

Result:

[4] -> [5] -> [6] -> [7] -> [0] -> [1] -> [2]
 target found at index 4

Annotated Code

DSA C

#include <stdio.h>

int search(int* nums, int numsSize, int target) {
    int low = 0, high = numsSize - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (nums[mid] == target) {
            return mid; // found target
        }
        // Check if left half is sorted
        if (nums[low] <= nums[mid]) {
            // Check if target is in left half
            if (nums[low] <= target && target < nums[mid]) {
                high = mid - 1; // search left half
            } else {
                low = mid + 1; // search right half
            }
        } else {
            // Right half is sorted
            if (nums[mid] < target && target <= nums[high]) {
                low = mid + 1; // search right half
            } else {
                high = mid - 1; // search left half
            }
        }
    }
    return -1; // target not found
}

int main() {
    int nums[] = {4,5,6,7,0,1,2};
    int target = 0;
    int size = sizeof(nums) / sizeof(nums[0]);
    int index = search(nums, size, target);
    if (index != -1) {
        printf("Target %d found at index %d\n", target, index);
    } else {
        printf("Target %d not found\n", target);
    }
    return 0;
}

while (low <= high) {

loop to narrow search range until low passes high

int mid = low + (high - low) / 2;

calculate middle index to split search

if (nums[mid] == target) { return mid; }

check if mid is target, return index if yes

if (nums[low] <= nums[mid]) {

check if left half is sorted

if (nums[low] <= target && target < nums[mid]) { high = mid - 1; } else { low = mid + 1; }

decide to search left or right half based on target position

else { if (nums[mid] < target && target <= nums[high]) { low = mid + 1; } else { high = mid - 1; } }

right half sorted, decide search side similarly

Output

Target 0 found at index 4

Complexity Analysis

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

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

vs Alternative: Compared to linear search O(n), this binary search approach is much faster on large arrays

Edge Cases

empty array

returns -1 immediately because low > high

DSA C

while (low <= high) {

array with one element matching target

returns index 0 immediately

DSA C

if (nums[mid] == target) { return mid; }

target not in array

returns -1 after search space is exhausted

DSA C

return -1;

When to Use This Pattern

When you see a sorted array that has been rotated and need to find an element quickly, use this modified binary search that checks which half is sorted to decide where to search next.

Common Mistakes

Mistake: Not checking which half is sorted before deciding search direction
Fix: Always check if left half or right half is sorted before comparing target

Mistake: Using mid = (low + high) / 2 without preventing overflow
Fix: Use mid = low + (high - low) / 2 to avoid integer overflow

Summary

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

Use when you have a sorted array rotated at some pivot and need fast search.

The key is to identify which half is sorted and decide search direction accordingly.

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