Search in Rotated Sorted Array Using Binary Search in C

Searching in a rotated sorted array is a classic problem that extends the concept of binary search.

Instead of a fully sorted array, the array is rotated at some pivot, making direct binary search ineffective.

However, by identifying which half of the array is sorted at each step, we can still achieve efficient search.

Concept Overview

A rotated sorted array is created by rotating a sorted array at some pivot point.

Example: Sorted array [1,2,3,4,5,6] → Rotated: [4,5,6,1,2,3]

At least one half of the array remains sorted at any step.

Problem Statement

Given a rotated sorted array and a target value, return its index if found, otherwise return -1.

Example

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

Output:
Index: 4

Approach (Modified Binary Search)

1. Initialize low = 0 and high = n-1.

2. Find mid = (low + high) / 2.

3. If arr[mid] equals target, return mid.

4. Check which half is sorted.

5. If left half is sorted, check if target lies in it.

6. Otherwise, search in right half.

7. Repeat until found or range is exhausted.

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 mid;

        // Left half is sorted
        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 -1;
}

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

    int result = search(arr, n, target);

    if (result != -1)
        printf("Element found at index: %d", result);
    else
        printf("Element not found");

    return 0;
}

Output

Element found at index: 4

Detailed Explanation

At each step, we determine which part of the array is sorted.

We then decide whether the target lies in that sorted half.

This reduces the search space just like binary search.

Time and Space Complexity

Time Complexity: O(log n)

Space Complexity: O(1)

Applications

Used in search systems with rotated or shifted datasets.

Common in interview and competitive programming problems.

Advantages

Maintains logarithmic time complexity.

Efficient for large datasets.

Limitations

More complex than standard binary search.

Handling duplicates requires additional logic.

Improvements You Can Make

Extend the solution to handle duplicate elements.

Find the rotation pivot separately.

Combine with other search optimizations.

Mastering this variation of binary search is essential for solving many advanced array problems.