Skip to main content

Leetcode 81: Search in Rotated Sorted Array II

 

1. Problem Statement (Simple Explanation)


You’re given:

  • A rotated array nums that was originally sorted in non-decreasing order.

  • The array may contain duplicates.

  • An integer target.

You must return:

  • true if target exists in nums

  • false otherwise.

Rotation:

  • Original sorted: e.g. [0,1,2,4,4,4,5,6,6,7]

  • Rotated at pivot k: e.g. [4,5,6,6,7,0,1,2,4,4]

Goal: Decrease operations as much as possible (use a modified binary search).


2. Examples


Example 1:


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

0 is in the array.

Output: true


Example 2:


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

3 is not in the array.

Output: false


3. Approach – Modified Binary Search (with duplicates)


This is similar to LeetCode 33 but now nums may contain duplicates.

Without duplicates:

  • At each step we could tell which half is sorted and then decide which side to search.

With duplicates, especially when nums[left] == nums[mid] == nums[right], we lose the ability to clear-cut decide which half is sorted.


Key Idea:


We still use binary search with pointers:

  • left = 0

  • right = n - 1

At each iteration:

  1. Compute mid.

  2. If nums[mid] == target → return true.

  3. If there are duplicates that blur the order:

    • When nums[left] == nums[mid] == nums[right]:

      • We cannot determine which side is sorted.

      • To make progress, shrink the search space:

left++

right--

  • This is the key difference from problem 33.

  1. Otherwise, at least one side is strictly increasing enough to reason.

We then use the standard rotated-array logic (like LeetCode 33):

  • If left half is sorted: nums[left] <= nums[mid]:

    • If nums[left] <= target < nums[mid], the target is in the left half → right = mid - 1.

    • Else → search right half → left = mid + 1.

  • Else (right half is sorted):

    • If nums[mid] < target <= nums[right], target is in the right half → left = mid + 1.

    • Else → search left half → right = mid - 1.

If the loop terminates without finding target, return false.


Pseudo-code:



Complexity & Follow-up:


  • In the average case, this is close to O(log n) like standard binary search.

  • However, due to duplicates, worst-case behavior can degrade to O(n):

    • e.g. [1,1,1,1,1] or [1,1,1,1,2,1,1] with target 2.

    • The step where nums[left] == nums[mid] == nums[right] forces us to shrink boundaries by 1, leading to O(n).


Answer to follow-up:


Yes, duplicates can affect the runtime complexity. In the worst case, when at many steps nums[left] == nums[mid] == nums[right], we cannot determine which half is sorted and are forced to move left++ and right--, which degrades the worst-case complexity from O(log n) to O(n).


4. Java code



5. C code



6. C++ code



7. Python code



8. JavaScript code


Comments

Post a Comment