Search in Rotated Sorted Array with Duplicates in C

Searching in a rotated sorted array becomes more complex when duplicate elements are present.

Standard binary search logic needs modification because duplicates can hide the sorted half.

In this tutorial, we will handle these edge cases efficiently.

Concept Overview

In rotated arrays, at least one half is usually sorted.

However, duplicates may make both halves appear identical.

In such cases, we shrink the search space linearly.

Problem Statement

Given a rotated sorted array that may contain duplicates, determine if a target element exists.

Example

Input:
Array: 2 5 6 0 0 1 2
Target: 0

Output:
Element Found

Approach (Modified Binary Search)

1. Initialize low and high pointers.

2. Calculate mid index.

3. If target matches mid, return true.

4. If duplicates exist (arr[low] == arr[mid] == arr[high]), shrink range.

5. Identify sorted half and search accordingly.

6. Repeat until element is found or range ends.

C Program

#include <stdio.h>

int search(int arr[], int n, int target) {
    int low = 0, high = n - 1;

    while (low <= high) {
        int mid = (low + high) / 2;

        if (arr[mid] == target)
            return 1;

        // Handle duplicates
        if (arr[low] == arr[mid] && arr[mid] == arr[high]) {
            low++;
            high--;
        }
        // Left half is sorted
        else if (arr[low] <= arr[mid]) {
            if (target >= arr[low] && target < arr[mid])
                high = mid - 1;
            else
                low = mid + 1;
        }
        // Right half is sorted
        else {
            if (target > arr[mid] && target <= arr[high])
                low = mid + 1;
            else
                high = mid - 1;
        }
    }

    return 0;
}

int main() {
    int arr[] = {2, 5, 6, 0, 0, 1, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 0;

    if (search(arr, n, target))
        printf("Element Found");
    else
        printf("Element Not Found");

    return 0;
}

Output

Element Found

Detailed Explanation

The algorithm extends binary search to handle duplicates.

When all three values (low, mid, high) are equal, we shrink the search range.

Otherwise, we identify the sorted half and proceed normally.

Time and Space Complexity

Time Complexity: O(log n) in average case.

Worst Case: O(n) due to duplicates.

Space Complexity: O(1)

Applications

Used in real-world search systems with repeated data.

Applicable in database queries and log analysis.

Advantages

Handles duplicate elements effectively.

Still efficient in most cases.

Limitations

Worst-case performance degrades to linear time.

More complex logic than standard binary search.

Improvements You Can Make

Optimize duplicate handling strategies.

Combine with pivot-based search.

Extend to return index instead of boolean.

This problem is crucial for mastering advanced variations of binary search in C.