Find a Value in a Rotated Sorted Array That May Contain Duplicates

Medium20–25 min

Topics

ArrayBinary Search

Companies

AmazonMicrosoftFacebook

This is a follow-up to searching a rotated sorted array, except nums may now contain duplicate values. Given the rotated array nums and an integer target, return true if target is present, or false otherwise. Duplicates mean nums[lo], nums[mid], and nums[hi] can all tie, making it impossible to tell which half is sorted — when that happens, shrink both ends inward by one and try again. This pushes the worst case to O(n), but the algorithm still behaves like binary search whenever the tie doesn't occur.

Test Case 1:

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

Output:true

Explanation:0 appears at index 3 (and again at index 4).

Test Case 2:

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

Output:false

Explanation:3 never appears in nums.

Test Case 3:

Input:nums = [3, 1, 2, 3, 3, 3, 3], target = 1

Output:true

Explanation:Repeated 3s on both ends make it briefly impossible to tell which half is sorted.

Constraints

◆1 ≤ nums.length ≤ 5000
◆-10⁴ ≤ nums[i] ≤ 10⁴
◆nums was sorted in non-decreasing order, then rotated at some unknown pivot
◆nums may contain duplicate values
◆-10⁴ ≤ target ≤ 10⁴

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

🧪Try your own test case

nums (rotated sorted, may repeat) — 1-12 integerstarget

1	class Solution {
2	public boolean searchRotatedWithDuplicates(int[] nums, int target) {
3	int lo = 0, hi = nums.length - 1;
4	while (lo <= hi) {
5	int mid = lo + (hi - lo) / 2;
6	if (nums[mid] == target) return true;
7	if (nums[lo] == nums[mid] && nums[mid] == nums[hi]) {
8	lo++;
9	hi--;
10	} else if (nums[lo] <= nums[mid]) {
11	if (nums[lo] <= target && target < nums[mid]) {
12	hi = mid - 1;
13	} else {
14	lo = mid + 1;
15	}
16	} else {
17	if (nums[mid] < target && target <= nums[hi]) {
18	lo = mid + 1;
19	} else {
20	hi = mid - 1;
21	}
22	}
23	}
24	return false;
25	}
26	}
27

↑lo

↑hi

Variables

lo0

hi6

INITIALIZE

Search the full range [0, 6] for target 1. Unlike the duplicate-free version, nums[lo] and nums[mid] can now tie even when we can't tell which half is sorted.

Step 1 / 4

Approach & Solutions

Brute Force — Linear Scan

Brute

Duplicates or not, a plain left-to-right scan always works — check every value against target. It's correct on any input, but it gives up the O(log n) speed that binary search would normally offer on a (mostly) sorted array.

TimeO(n)

SpaceO(1)

Java

Try it out

class Solution {
    public boolean searchRotatedWithDuplicates(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) return true;
        }
        return false;
    }
}

Optimal — Modified Binary Search with Duplicate Handling

Optimal

Same idea as the duplicate-free version — figure out which half is sorted and search there if target fits its range — except duplicates can make nums[lo], nums[mid], and nums[hi] all equal, which hides which half is actually sorted. When that happens, there's no shortcut: shrink lo and hi inward by one and try again. That fallback is what pushes the worst case to O(n).

TimeO(log n) average, O(n) worst case