DSA Modified Binary Search

Search in Rotated Sorted Array II

Same as version I but values may duplicate — strip equal endpoints to recover monotonicity, worst-case O(n).

Medium
Time O(log n) avg Space O(1)
LeetCode
4 min read
binary-search

Problem#

Rotated sorted array, possibly with duplicates. Return true iff target exists.

Examples#

  • nums = [2,5,6,0,0,1,2], target = 0 → true
  • nums = [2,5,6,0,0,1,2], target = 3 → false

Constraints#

  • 1 <= n <= 5000.

Hints#

Hint 1
When nums[lo] == nums[mid] == nums[hi], you can’t tell which half is sorted — shrink both ends by one.

Approach#

Modified rotated search. The new case: if nums[lo] == nums[mid] == nums[hi], both ends could be the rotation point — strip them with ++lo; --hi. Otherwise the standard “one half is sorted” logic applies.

Solution#

Search in Rotated Sorted Array II
class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int lo = 0, hi = nums.size() - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] == target) return true;
            if (nums[lo] == nums[mid] && nums[mid] == nums[hi]) {
                ++lo; --hi;
            } else if (nums[lo] <= nums[mid]) {
                if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
                else lo = mid + 1;
            } else {
                if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
                else hi = mid - 1;
            }
        }
        return false;
    }
};

Editorial#

Duplicates at both ends destroy the binary-search invariant momentarily — we can’t tell which half is sorted. Stripping one element from each end preserves correctness (we’ve already checked mid) and amortizes to O(n) worst case, O(log n) typical.

Complexity#

  • Time: O(log n) typical, O(n) worst.
  • Space: O(1).

Concept revision#

Search ESC

Keyboard shortcuts

Shortcuts are disabled while typing in inputs.