← Back to Index

📚 Search in Rotated Sorted Array – Java Cheat Sheet

📌 What Is It?

The Search in Rotated Sorted Array problem involves finding a target element in a sorted array that has been rotated at an unknown pivot. The goal is to locate the target in O(log N) time using binary search.

🧱 Pattern Template

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

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

            // Determine which half is sorted
            if (nums[left] <= nums[mid]) { // Left half is sorted
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1; // Search left half
                } else {
                    left = mid + 1; // Search right half
                }
            } else { // Right half is sorted
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1; // Search right half
                } else {
                    right = mid - 1; // Search left half
                }
            }
        }

        return -1; // Target not found
    }
}

📊 Time Complexity

• Binary Search: O(log N) – Halving the search space at each step.

✅ Use Cases

• Searching in rotated sorted arrays
• Finding elements in arrays with unknown pivots

📘 Common LeetCode Problems

• 33. Search in Rotated Sorted Array [Medium] Binary Search
• 153. Find Minimum in Rotated Sorted Array [Medium] Binary Search

🧪 Example: Search in Rotated Sorted Array

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Explanation:
- The target 0 is found at index 4.

▶️ View Animation

💡 Pro Tips

• Always check which half of the array is sorted to decide the search direction.
• Edge cases: arrays with duplicates, single-element arrays, or when the target is not present.