Search a rotated array with repeated values
An array of integers, sorted in non-decreasing order and possibly containing repeated values, has been
rotated at an unknown point. Given the rotated array nums and a target, return
true if target occurs in it and false otherwise.
Examples
| Input | Output | Why |
|---|---|---|
nums = [2, 5, 6, 0, 0, 1, 2], target = 0 | true | |
nums = [2, 5, 6, 0, 0, 1, 2], target = 3 | false | |
nums = [1, 0, 1, 1, 1], target = 0 | true | The ends and the middle are all 1: the 0 could be on either side. |
Constraints
- 1 ≤ n ≤ 5000
- −10⁴ ≤ nums[i], target ≤ 10⁴
Hints
Hint 1
Start from the distinct-values version: compare nums[lo] with nums[mid] to find the sorted half.
Hint 2
Try [1, 0, 1, 1, 1] and [1, 1, 1, 0, 1]. Both have nums[lo] = nums[mid] = nums[hi] = 1, but the 0 is on different sides.
Hint 3
In that case, nums[lo] and nums[hi] are not the target (nums[mid] already was not), so both can be dropped: lo += 1, hi −= 1.
Where people lose marks
- Treating nums[lo] ≤ nums[mid] as proof that the left half is sorted when nums[hi] is the same value as well.
- Claiming O(log n) for every input: an interviewer will ask for the worst case.
- Shrinking only one end in the ambiguous case: correct, but it needs a separate argument that the dropped end is not the target.
Dry run on [3,3,3,3,3,3,1,2,3],2
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 5target2
Looking for 2 in a rotated array with repeats.
-
Step 2 / 5lo0mid4hi8
nums[0] = nums[4] = nums[8] = 3. Either half could hold the break, so neither can be discarded. But 3 is not 2, so the two ends can go: lo = 1, hi = 7.
-
Step 3 / 5lo1mid4hi7
nums[1] = 3 ≤ nums[4] = 3 and the ends differ, so the left half is sorted. 2 is not between 3 and 3: lo = 5.
-
Step 4 / 5lo5mid6hi7
nums[5] = 3 > nums[6] = 1: the right half is sorted. 2 is between 1 and 2: lo = 7.
-
Step 5 / 5lo7mid7hi7
nums[7] = 2: found. Return true.
How to think about it
The distinct-values search decides which half is sorted by comparing nums[lo] with
nums[mid]. With repeats there is one case where that fails: nums[lo] = nums[mid] = nums[hi].
Both [1, 0, 1, 1, 1] and [1, 1, 1, 0, 1] look the same from those three positions, with
the break on opposite sides.
In that case the search cannot discard half, but it can discard two elements. nums[mid] has just
been compared with the target and is not it, and the two ends hold the same value, so neither end is the target
either: lo += 1, hi −= 1. In every other case one half is sorted and the
distinct-values logic applies, with one check: if nums[lo] = nums[mid] but nums[hi]
differs, the left half is all one value and is sorted.
The worst case is now O(n): an array of 1s with a single 0 forces the search to strip the ends one at a time. No algorithm can do better, since it must look at every position to find where the 0 is. Saying so is part of a complete answer.
Complexity. Time O(log n) typical, O(n) worst case · Space O(1)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def search_rotated_dups(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
return True
if nums[lo] == nums[mid] == nums[hi]: # cannot tell which half is sorted
lo += 1 # but neither end is the target
hi -= 1
elif nums[lo] <= nums[mid]: # left half is sorted
if nums[lo] <= target < nums[mid]:
hi = mid - 1
else:
lo = mid + 1
else: # right half is sorted
if nums[mid] < target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
return False#include <vector>
bool solve(const std::vector<int>& nums, int target) {
int lo = 0, hi = (int)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; } // ambiguous: drop both ends
else if (nums[lo] <= nums[mid]) { // left half is sorted
if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
else lo = mid + 1;
} else { // right half is sorted
if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
else hi = mid - 1;
}
}
return false;
}class Solution {
public boolean searchRotatedDups(int[] nums, int target) {
int lo = 0, hi = nums.length - 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--; } // ambiguous
else if (nums[lo] <= nums[mid]) { // left half is sorted
if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
else lo = mid + 1;
} else { // right half is sorted
if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
else hi = mid - 1;
}
}
return false;
}
}function searchRotatedDups(nums, target) {
let lo = 0, hi = nums.length - 1;
while (lo <= hi) {
const mid = lo + ((hi - lo) >> 1);
if (nums[mid] === target) return true;
if (nums[lo] === nums[mid] && nums[mid] === nums[hi]) { lo++; hi--; } // ambiguous: drop both ends
else if (nums[lo] <= nums[mid]) { // left half is sorted
if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
else lo = mid + 1;
} else { // right half is sorted
if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
else hi = mid - 1;
}
}
return false;
}fn solve(nums: &[i64], target: i64) -> bool {
let (mut lo, mut hi) = (0i64, nums.len() as i64 - 1);
while lo <= hi {
let mid = lo + (hi - lo) / 2;
let (l, m, h) = (nums[lo as usize], nums[mid as usize], nums[hi as usize]);
if m == target {
return true;
}
if l == m && m == h { // ambiguous: drop both ends
lo += 1;
hi -= 1;
} else if l <= m { // left half is sorted
if l <= target && target < m { hi = mid - 1 } else { lo = mid + 1 }
} else { // right half is sorted
if m < target && target <= h { lo = mid + 1 } else { hi = mid - 1 }
}
}
false
}import Data.Array
solve :: [Int] -> Int -> Bool
solve nums target = go 0 (n - 1)
where
n = length nums
a = listArray (0, n - 1) nums
go lo hi
| lo > hi = False
| m == target = True
| l == m && m == h = go (lo + 1) (hi - 1) -- ambiguous: drop both ends
| l <= m = if l <= target && target < m then go lo (mid - 1) else go (mid + 1) hi
| otherwise = if m < target && target <= h then go (mid + 1) hi else go lo (mid - 1)
where
mid = lo + (hi - lo) `div` 2
(l, m, h) = (a ! lo, a ! mid, a ! hi)Variants to try
- Find the minimum of a rotated array with duplicates: when nums[mid] = nums[hi], drop hi only.
- Return the index of the first occurrence of target: the ambiguous case breaks the usual argument, so search for the rotation point first.
Next problems
Minimum of a rotated sorted array
The input is not sorted, so the usual comparison is useless. Compare against the right end instead.
Open the problem → Medium20 minFind a value in a rotated sorted array
Split any range at its middle and one side is in order. Test whether the target lies in that side; if not, it lies in the other.
Open the problem → Easy10 minFind a value in a sorted array
The search every other binary search is built on: halve a closed range until the value is found or the range is empty.
Open the problem →Write a solution and run it against the real test table.
Keep going
Minimum of a rotated sorted array
The input is not sorted, so the usual comparison is useless. Compare against the right end instead.
Open the problem → Medium20 minFind a value in a rotated sorted array
Split any range at its middle and one side is in order. Test whether the target lies in that side; if not, it lies in the other.
Open the problem → Easy10 minFind a value in a sorted array
The search every other binary search is built on: halve a closed range until the value is found or the range is empty.
Open the problem → Binary searchThe pattern behind it
Search the answer, not the array: halve a monotone predicate until one candidate is left.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.