In this blog post, we’ll explore how to solve the LeetCode problem of searching for a target value in a sorted array that has been rotated an unknown number of times. This is a fascinating challenge that combines the elegance of binary search with the twist of handling a rotated structure. Let’s dive into the problem.

---

Problem Statement

We are given an array nums that is sorted in ascending order and has been rotated between 1 and n times, where n is the length of the array. Our task is to find the index of a given integer target in nums. If the target exists, we return its index; otherwise, we return -1. The array contains no duplicates, which simplifies our logic, and we aim to solve this efficiently, ideally in O(log n) time.

Sample Input and Output

Example 1:

• Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 0
• Output: 4
• Explanation: The target 0 is found at index 4.

Example 2:

• Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 3
• Output: -1
• Explanation: The target 3 is not present in the array.

---

Thought Process Behind the Approach

What Does “Rotated Sorted” Mean?

• Original Array: A sorted array like [0, 1, 2, 4, 5, 6, 7].
• After Rotation: Becomes [4, 5, 6, 7, 0, 1, 2] after rotating at some point.
• Key Property: The array is split into two parts around a “pivot” (the smallest element), and each part is sorted within itself.

Why Binary Search?

• Standard Binary Search: Works on fully sorted arrays by cutting the search space in half each step.
• Here: The array isn’t fully sorted, but at least one half (left or right of the middle) is always sorted.
• Goal: Use this sorted half to decide where to search next.

Step 3: Finding the Sorted Half

• How to Check:
  • Pick the middle element (mid).
  • Compare nums[left] (start) with nums[mid]:
    • If nums[left] <= nums[mid], the left half (left to mid) is sorted.
    • If not, the right half (mid to right) is sorted.
• Why This Works: In a rotated sorted array without duplicates, the sorted half is always uninterrupted.

Step 4: Where Is the Target?

• If Left Half is Sorted:
  • Range is nums[left] to nums[mid].
  • Check: Is nums[left] <= target <= nums[mid]?
    • Yes: Target is in the left half.
    • No: Target must be in the right half.
• If Right Half is Sorted:
  • Range is nums[mid] to nums[right].
  • Check: Is nums[mid] <= target <= nums[right]?
    • Yes: Target is in the right half.
    • No: Target must be in the left half.

Step 5: Adjusting the Search

• Left Half Sorted and Target in Range:
  • Move right = mid - 1 to search left.
• Left Half Sorted but Target Not in Range:
  • Move left = mid + 1 to search right.
• Right Half Sorted and Target in Range:
  • Move left = mid + 1 to search right.
• Right Half Sorted but Target Not in Range:
  • Move right = mid - 1 to search left.

Walking Through Examples

Example 1: Target in Left Sorted Half

• Array: [4, 5, 6, 7, 0, 1, 2], Target: 6
• Initial State: - left = 0, right = 6, mid = 3 - nums[left] = 4, nums[mid] = 7 - 4 <= 7, so left half [4, 5, 6, 7] is sorted.
• Check Range: - 4 <= 6 <= 7? Yes, search left: right = 2.
• Next Step: - left = 0, right = 2, mid = 1 - nums[mid] = 5 < 6, left half sorted, 4 <= 6 <= 5? No, left = 2.
• Final Step: - left = 2, right = 2, mid = 2 - nums[mid] = 6, found at index 2.

Example 2: Target in Right Sorted Half

• Array: [6, 7, 0, 1, 2, 4, 5], Target: 4
• Initial State: - left = 0, right = 6, mid = 3 - nums[left] = 6, nums[mid] = 1 - 6 > 1, so right half [1, 2, 4, 5] is sorted.
• Check Range: - 1 <= 4 <= 5? Yes, search right: left = 4.
• Next Step: - left = 4, right = 6, mid = 5 - nums[mid] = 4, found at index 5.

Example 3: Target at Pivot

• Array: [3, 4, 5, 1, 2], Target: 1
• Initial State: - left = 0, right = 4, mid = 2 - nums[left] = 3, nums[mid] = 5 - 3 <= 5, left half [3, 4, 5] is sorted.
• Check Range: - 3 <= 1 <= 5? No, search right: left = 3.
• Next Step: - left = 3, right = 4, mid = 3 - nums[mid] = 1, found at index 3.

Edge Cases

• One Element: [1], target 1 → Check and return 0.
• No Rotation: [1, 2, 3, 4], target 3 → Works as standard binary search.
• Target at Ends: [2, 1], target 2 or 1 → Logic covers both.

Why It’s Efficient

• Always a Sorted Half: Guarantees we can decide where to search.
• Halving Each Step: Keeps time complexity at O(log n).

Algorithm

Here’s the step-by-step algorithm:

1. Base Case: If the array is null or empty, return -1.
2. Initialize Pointers: Set left = 0 and right = nums.length - 1.
3. Binary Search Loop: While left <= right:
   • Compute mid = left + (right - left) / 2 (to avoid integer overflow).
   • If nums[mid] == target, return mid.
   • Check Left Half: If nums[left] <= nums[mid], the left half is sorted.
     • If nums[left] <= target < nums[mid], set right = mid - 1.
     • Else, set left = mid + 1.
   • Check Right Half: Else, the right half is sorted.
     • If nums[mid] < target <= nums[right], set left = mid + 1.
     • Else, set right = mid - 1.
4. Not Found: If the loop exits, return -1.

This ensures we leverage the sorted portion at each step to make an informed decision.

---

Java Code

Here’s the implementation with detailed comments:

public class Solution {
    public int search(int[] nums, int target) {
        // Handle null or empty array
        if (nums == null || nums.length == 0) {
            return -1;
        }
        
        int left = 0;
        int right = nums.length - 1;
        
        while (left <= right) {
            // Calculate middle index safely
            int mid = left + (right - left) / 2;
            
            // Target found
            if (nums[mid] == target) {
                return mid;
            }
            
            // Check if left half is sorted
            if (nums[left] <= nums[mid]) {
                // Check if target is in the left half's range
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1; // Search left
                } else {
                    left = mid + 1;  // Search right
                }
            } 
            // Right half must be sorted
            else {
                // Check if target is in the right half's range
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;  // Search right
                } else {
                    right = mid - 1; // Search left
                }
            }
        }
        
        // Target not found
        return -1;
    }
}

---

Key Points

• Efficiency: The algorithm runs in O(log n) time, matching the performance of binary search, by halving the search space each iteration.
• Space Complexity: Uses O(1) extra space, relying only on a few variables.

---

Happy leetcoding!🚀