🧩 Search in Rotated Sorted Array (Java)

🚀 Problem Statement

You are given:

• A sorted array that has been rotated
• A target value

Your task:

• Return the index of target
• If not found, return -1
• Must run in O(log n) time

---

💡 Key Idea

Even after rotation:
👉 At least one half of the array is always sorted

So in binary search:

• Identify which half is sorted
• Check if target lies in that half
• Narrow the search accordingly

---

🧠 Intuition

For any mid:

• If nums[low] <= nums[mid] → left half is sorted
• Else → right half is sorted

Then:

• Check if target lies in the sorted half
• Move left or right accordingly

---

🛠️ Java Implementation

```java id="m2k9zx"
class Solution {
public int search(int[] nums, int target) {
int low = 0, high = nums.length - 1;

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

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

        // Left half is sorted
        if (nums[low] <= nums[mid]) {
            if (target >= nums[low] && target < nums[mid]) {
                high = mid - 1; // search left
            } else {
                low = mid + 1;  // search right
            }
        }
        // Right half is sorted
        else {
            if (target > nums[mid] && target <= nums[high]) {
                low = mid + 1;  // search right
            } else {
                high = mid - 1; // search left
            }
        }
    }

    return -1; // not found
}

}

---

## 🔍 Example



```text id="0q3x7n"
Input:
nums = [4,5,6,7,0,1,2], target = 0

Output:
4

---

⏱️ Complexity Analysis

Type	Complexity
Time	O(log n)
Space	O(1)

---

📌 Key Observations

• One half is always sorted
• Use that to eliminate half of the search space
• Similar to binary search but with extra condition

---

⚠️ Common Mistakes

❌ Forgetting to check which half is sorted
❌ Using normal binary search (won’t work here)
❌ Wrong boundary conditions

---

🎯 Final Thoughts

This is a must-know interview problem because it tests:

• Binary search mastery
• Logical reasoning
• Edge case handling