Practice/Microsoft/Leetcode 81. Search in Rotated Sorted Array II

Leetcode 81. Search in Rotated Sorted Array II

CodingOptional

Problem

You are given an array that was originally sorted in non-decreasing order (elements can repeat), but has been rotated around some unknown pivot point. For example, the array [0, 1, 2, 4, 5, 6, 7] might become [4, 5, 6, 7, 0, 1, 2] after rotation.

Your task is to determine whether a given target value exists anywhere in this rotated array. Return true if the target is found, false otherwise.

The challenge lies in efficiently searching this array despite:

• The rotation breaking the sorted order at one point
• The presence of duplicate values which can obscure which portion is properly sorted

Requirements

1. Return true if the target exists in the array, false otherwise
2. Handle arrays that may contain duplicate elements
3. Handle arrays of any valid length including single elements
4. Account for the fact that the array has been rotated at an unknown pivot point

Constraints

• 1 ≤ nums.length ≤ 5000
• -104 ≤ nums[i] ≤ 104
• nums is guaranteed to be sorted in non-decreasing order before rotation
• -104 ≤ target ≤ 104
• Try to minimize the average time complexity (aim for better than O(n) when possible)

Examples

Example 1:

Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 0 Output: true Explanation: The value 0 exists in the array at index 4

Example 2:

Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 3 Output: false Explanation: The value 3 does not exist in the array

Example 3:

Input: nums = [2, 5, 6, 0, 0, 1, 2], target = 0 Output: true Explanation: Even with duplicate 2's and 0's, we can find that 0 exists

Example 4:

Input: nums = [1, 0, 1, 1, 1], target = 0 Output: true Explanation: Duplicates make it hard to determine which half is sorted, but 0 is present