Search in Rotated Sorted Array II - Video Solutions

Problem Overview: You are given a rotated sorted array that may contain duplicates. The task is to determine whether a target value exists in the array. Unlike the classic rotated array problem, duplicates make it harder to determine which side of the array is sorted, so the search logic needs extra handling.

Approach 1: Modified Binary Search (Average O(log n), Worst O(n) time, O(1) space)

This approach adapts binary search to handle rotation and duplicates. Start with two pointers left and right, compute mid, and check if nums[mid] equals the target. Normally, one half of the rotated array is sorted, which allows you to discard half the search space. The complication appears when nums[left] == nums[mid] == nums[right]; duplicates prevent you from identifying the sorted side. In that case, shrink the window by incrementing left and decrementing right.

If the left half is sorted (nums[left] <= nums[mid]), check whether the target lies between nums[left] and nums[mid]. If it does, move right = mid - 1; otherwise search the other half. If the right half is sorted, apply the same logic symmetrically. This method still behaves like classic rotated-array search in most cases, giving O(log n) performance. However, arrays filled with duplicates can force repeated shrinking of the window, degrading to O(n).

The algorithm uses only index comparisons and constant extra memory, making it efficient and suitable for large arrays. Since the problem revolves around rotated ordering and conditional partitioning, it heavily relies on array traversal combined with decision logic typical in binary search problems.

Approach 2: Linear Search (Fallback) (O(n) time, O(1) space)

The simplest solution iterates through the entire array and checks whether any element equals the target. Use a single loop from index 0 to n-1 and return true when a match is found. If the loop completes without finding the target, return false. This approach ignores the rotated sorted structure completely.

Linear search works reliably regardless of duplicates, rotations, or array ordering. It also becomes the theoretical worst-case behavior of the modified binary search when duplicates prevent meaningful partitioning. While not optimal for large inputs, it is trivial to implement and useful as a correctness baseline or fallback during debugging.

Recommended for interviews: Interviewers expect the modified binary search solution. It shows you understand how rotation affects ordering and how duplicates complicate the decision about which half is sorted. Mentioning the linear scan demonstrates awareness of the brute-force baseline, but implementing the binary search variation shows stronger algorithmic reasoning.