Problem Statement
Search in Rotated Sorted Array II
Start with a sorted list of numbers, then "rotate" it: cut it somewhere and move the front chunk to the back. So [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]. This version also allows duplicates, meaning the same number can show up more than once. You are given a target number, and you need to return true if it is somewhere in the list, false if it is not. The clever idea here is binary search. Binary search is like looking up a word in a dictionary: you flip to the middle, see if your word comes before or after, and throw away the half you do not need. You keep halving until you find it or run out of pages. That only works because the dictionary is in order. Our list is rotated, so it is not fully in order, but here is the key fact: when you cut a sorted list and rotate it, at least one of the two halves around the middle is still perfectly sorted. So at each step we figure out which half is sorted, check if the target could live in that sorted half, and jump to the right side. The one annoying case is duplicates: when the value at the left, the middle, and the right are all the same, we cannot tell which half is sorted, so we just nudge the edges inward by one and keep going.
Signals to notice
Brute force first
Linear scan — O(n).
The key insight
Modified binary search: when left == mid == right, shrink both ends. Otherwise, standard rotated array logic. Average O(log n), worst O(n).
Trace it on nums=[1,0,1,1,1], target=0
left=0, right=4, mid=2: nums[2]=1 != 0; nums[left]=nums[mid]=nums[right]=1 (all equal, half unknown) -> shrink both: left=1, right=3 left=1, right=3, mid=2: nums[2]=1 != 0; not all equal; nums[left]=0 <= nums[mid]=1 so LEFT half sorted check 0 <= target(0) < 1 -> true, target in sorted left -> right=mid-1=1 left=1, right=1, mid=1: nums[1]=0 == target -> return True
What must stay true
Duplicates prevent determining which half is sorted when left == mid == right. Shrinking by one is the only safe option.
Shape of the loop
left, right = 0, n-1 while left <= right: mid = (left+right)//2 if nums[mid] == target: return True if nums[left]==nums[mid]==nums[right]: left++, right-- # ambiguous: shrink elif nums[left] <= nums[mid]: # left half sorted -> pick side by target else: # right half sorted -> pick side by target return False
Pseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Not handling the ambiguous case — without it, you eliminate the wrong half.