Leetcode 33: Search in Rotated Sorted Array

1. Problem Statement (Simple Explanation):

You’re given:

• An array nums, originally sorted in ascending order with distinct values.

• It has been rotated at some unknown index k (0 ≤ k < n).

• An integer target.

The rotated array looks like:

• [nums[k], nums[k+1], ..., nums[n-1], nums[0], ..., nums[k-1]]

You must:

• Return the index of target in nums if it exists.

• Otherwise, return -1.

You must achieve O(log n) time → so you need a variant of binary search.

2. Examples:

Example 1:

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

0 is at index 4.

Output: 4

Example 2:

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

3 is not in the array.

Output: -1

Example 3:

Input: nums = [1], target = 0

0 is not in the array.

Output: -1

Constraints:

• 1 <= nums.length <= 5000

• -104 <= nums[i] <= 104

• All nums[i] are unique.

• nums is sorted ascending then possibly rotated.

• -104 <= target <= 104

3. Approach – Modified Binary Search (O(log n)):

We use binary search, but account for the rotation.

Key Observation:

Even though the array is rotated, at any mid point, at least one half is still properly sorted:

• Check nums[left] and nums[mid]:

• If nums[left] <= nums[mid] → the left half [left..mid] is sorted.

• Else → the right half [mid..right] is sorted.

Once we know which half is sorted, we can decide whether target lies in that half or in the other half.

Algorithm (Step-by-Step):

1. Initialize:

• left = 0

• right = n - 1

2. While left <= right:

• Compute mid = left + (right - left) / 2.

• If nums[mid] == target, return mid.

• Determine which half is sorted:

Case 1 – Left half sorted:

if nums[left] <= nums[mid]:

Then:

Check if target is within this sorted left half:

if nums[left] <= target < nums[mid]:

    right = mid - 1

else:

    left = mid + 1

Case 2 – Right half sorted:

else:

then right half [mid..right] is sorted:

Check if target is within that sorted right half:

if nums[mid] < target <= nums[right]:

    left = mid + 1

else:

    right = mid - 1

3. If the loop ends without finding target, return -1.

This works because we always discard half of the search space, ensuring O(logn) time.

Pseudo-code:

Complexity:

Let n = len(nums):

• Time: O(logn)

• Space: O(1)

Meets the requirement.

4. Java code:

5. C code:

6. C++ code:

7.  Python code:

8. JavaScript code: