1. Problem Statement

You are given an integer array nums that was originally sorted in ascending order, but then rotated at some pivot.

For example:

Original:       [0,1,2,4,5,6,7]
After rotation: [4,5,6,7,0,1,2]

Given the rotated array nums and an integer target, return the index of target if it is in nums. Otherwise, return -1.

1.1 Constraints:

• No duplicate elements.
• Time complexity must be O(log n) → Binary Search.

1.2 Example

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

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

2. Intuition

Even though the array is not fully sorted, it is a rotated sorted array. It still retains a key property:

At any point, one half of the array is always sorted.

This allows us to apply modified binary search.

3. Step-by-Step Approach

1. Start with two pointers:

• low at the beginning of the array.
• high at the end of the array.

2. While low is less than or equal to high, do the following:

• Find the mid (middle index).
• If nums[mid] is the target, return mid.

3. Now decide which half is sorted:

• If nums[low] <= nums[mid], then the left half is sorted.
  • Now check: is the target betweennums[low] and nums[mid]?
    • Yes → Target is in the left half → Move high = mid - 1
    • No → Target is in the right half → Move low = mid + 1
• Else, the right half is sorted.
  • Now check: is the target betweennums[mid] and nums[high]?
    • Yes → Target is in the right half → Move low = mid + 1
    • No → Target is in the left half → Move high = mid - 1

4. If you finish the loop and didn’t find the number → return -1.

4. Example Walkthrough (Target = 0)

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

• Step 1: low=0, high=6 → mid=3 → nums[3]=7
  • Left half [4,5,6,7] is sorted.
  • Target 0 is NOT in this range → search right: low = 4
• Step 2: low=4, high=6 → mid=5 → nums[5]=1
  • Right half [1,2] is sorted.
  • Target 0 is LESS than 1 → search left: high = 4
• Step 3: low=4, high=4 → mid=4 → nums[4]=0 → FOUND!

5. Java Code

public class RotatedSortedArraySearch {

    public int search(int[] nums, int target) {
        int low = 0;
        int high = nums.length - 1;

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

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

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

        return -1;
    }
}