DSA Day 61: Search in Rotated Sorted Array

📅 Date: April 5, 2026

🧠 Mood: The Logic Hacker 💻

🔥 Topic: DSA Day 61: Search in Rotated Sorted Array

🌀 When Binary Search Fails

Yesterday, I felt like a genius after mastering Binary Search. I thought I could find any element in $O(\log N)$ as long as the data was sorted. But then, I encountered a "Rotated" sorted array.

Imagine a sorted array like [0, 1, 2, 4, 5, 6, 7]. Now, rotate it at some pivot point. It becomes [4, 5, 6, 7, 0, 1, 2].

Suddenly, the "Golden Rule" of Binary Search—that the middle element always tells you which way to go—is broken. If you land on 7 and you are looking for 0, standard logic says "look left" because $0 < 7$. But in a rotated array, $0$ is actually on the right! This one simple rotation makes the standard algorithm completely useless.

---

💡 The One Sorted Half Rule

The trick to cracking this is a brilliant observation: No matter where you rotate the array, at least one half of it (either left of 'mid' or right of 'mid') will ALWAYS be sorted.

How to identify the sorted half?

• If arr[start] <= arr[mid], then the Left Half is sorted.
• Else, the Right Half is sorted.

Once you identify which half is sorted, you simply check if your target lies within that sorted range. If it does, you search there. If it doesn't, you throw that half away and search the other side. Simple, yet genius.

---

💻 The Modified Binary Search Code

#include <iostream>
#include <vector>
using namespace std;

int search(vector<int>& arr, int target) {
    int start = 0, end = arr.size() - 1;

    while (start <= end) {
        int mid = start + (end - start) / 2;

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

        // Step 1: Identify which half is sorted
        if (arr[start] <= arr[mid]) {
            // Left half is sorted
            if (target >= arr[start] && target < arr[mid]) {
                end = mid - 1; // Target is in the sorted left half
            } else {
                start = mid + 1; // Target is in the right half
            }
        } else {
            // Right half is sorted
            if (target > arr[mid] && target <= arr[end]) {
                start = mid + 1; // Target is in the sorted right half
            } else {
                end = mid - 1; // Target is in the left half
            }
        }
    }
    return -1;
}

int main() {
    vector<int> rotatedArray = {4, 5, 6, 7, 0, 1, 2};
    int target = 0;
    int index = search(rotatedArray, target);
    
    if(index != -1) cout << "Target found at index: " << index;
    else cout << "Target not found.";
    
    return 0;
}

---

🎯 Takeaway

Rotated Sorted Array search is the ultimate test of your binary search fundamentals. It still runs in O(log N) time, but the logic is far more robust. Tomorrow, we take a break from searching and start with a new data structure: Linked Lists. Get ready!