Abstract / Summary

Determine if a target value exists in a rotated sorted array that may contain duplicate elements.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 40% (3+ million submissions).

Typical patterns to solve this problem:

• Array
• Binary Search

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a Solution class with a search method that determines whether a given target integer exists in a list nums. The list may be rotated and may contain duplicate values, which complicates the classic binary-search approach. The algorithm employs a recursive helper named deeper that narrows the search interval while handling the special cases introduced by rotation and duplicates.

Core Logic

Entry Point

def search(self, nums: List[int], target: int) -> bool:
    return deeper(0, len(nums) - 1)

The method starts the recursion with the full range of indices, from 0 to len(nums) - 1.

Recursive Helper

def deeper(left, right):
    if nums[left] == target or nums[right] == target:
        return True

    if left >= right:
        return False

    pivot = (left + right) // 2
    if nums[pivot] == target:
        return True

The first three conditional blocks perform quick checks:

• The ends of the current interval are examined; if either matches the target, the search succeeds immediately.
• When the interval collapses (left >= right) without a match, the function returns False.
• The midpoint (pivot) is computed and compared to the target, providing the classic binary-search shortcut.

Determining Search Strategy

    if nums[left] < nums[right]:
        # basic binary search
        if nums[pivot] > target:
            return deeper(left, pivot - 1)
        else:
            return deeper(pivot + 1, right)
    else:
        # full search
        return deeper(left, pivot - 1) or deeper(pivot + 1, right)

The algorithm distinguishes two scenarios based on the relationship between the values at the current interval’s boundaries:

• Ordered Sub-array (nums[left] < nums[right]) - The segment is strictly increasing, so a standard binary-search decision can be made. If the midpoint value exceeds the target, the left half is explored; otherwise, the right half is explored.

• Potential Rotation or Duplicates (nums[left] >= nums[right]) - The ordering guarantee is lost. In this case the function cannot decide which side may contain the target, so it recursively searches both halves and combines the results with a logical OR. This ensures that any occurrence of the target in either sub-range is found.

Edge Cases Handled

• Single-Element List - The early boundary check (nums[left] == target or nums[right] == target) captures the only element, and the left >= right guard prevents further recursion.

• All Elements Identical - When every entry equals the same value, the condition nums[left] < nums[right] is false, causing the algorithm to fall back to the “full search” branch. The recursive OR exploration guarantees that the target is found if it matches the repeated value, and that the search terminates correctly when it does not.

• Empty List - The initial call uses right = len(nums) - 1. For an empty list right becomes -1, making left >= right true on the first invocation, and the function returns False without accessing any list element.

• Target at Interval Boundaries - The explicit check of nums[left] and nums[right] before any further division catches targets located at the edges of the current segment, avoiding unnecessary recursion.

Performance Optimizations

• Early Termination on Boundary Matches - By checking the leftmost and rightmost elements at each recursion level, the algorithm can often finish in constant time when the target lies at an interval edge.

• Pivot Equality Shortcut - The immediate comparison of nums[pivot] to the target eliminates the need for deeper exploration when the midpoint is the sought value.

• Selective Binary Search - When the current sub-array is confirmed to be sorted (nums[left] < nums[right]), the algorithm reduces the search space by half, preserving the logarithmic behavior of classic binary search for those portions.

• Short-Circuit OR Evaluation - In the “full search” branch, the expression deeper(left, pivot - 1) or deeper(pivot + 1, right) leverages Python’s short-circuit semantics. If the left recursive call finds the target, the right call is never executed, saving work in many practical cases.

• Avoidance of Extra Data Structures - The recursion operates directly on index boundaries, requiring only a constant amount of additional stack space per call and no auxiliary arrays or hash tables.

Flow Summary

The recursion proceeds by repeatedly narrowing the interval. When the interval is ordered, it behaves like a conventional binary search, halving the problem size each step. When ordering cannot be guaranteed because of rotation or duplicate values, the algorithm conservatively explores both halves, ensuring correctness at the cost of potentially higher recursion depth. The combination of early boundary checks, pivot comparison, and short-circuit logic provides a balanced approach that adapts to the structure of the input data while keeping the implementation concise.

Imagine a long row of numbered toy boxes placed in a line. Some boxes are sorted nicely from smallest to biggest, but some might be tumbled around a bit. The goal is to find if a specific special toy is hiding inside one of these boxes.

The code starts by looking at the very first box and the very last box in the long line. It checks if the special toy is right there at the ends. If it is not, the code picks the middle box to peek inside.

If the row of boxes looks like it is sorted properly, the code knows exactly which side to check next so it does not have to look through every single box. It simply cuts the line in half and decides whether to go left or right.

If the boxes are scrambled and do not follow a simple order, the code decides to be extra careful. It splits the line in half and chooses to search both sides, one after the other, until it finds the special toy. It keeps zooming in on smaller groups of boxes until the search is done.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python					Java		TS
	WalkCCC	C++	Python					Java
	leetcode.ca	C++	Python			Rust	JS	Java	Go	TS
	LeetcodeHelp	C++	Python					Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python					Java
github	aylei					Rust
	begeekmyfriend				C
	BigEggStudy			C#
	black-shadows	C++
	charles-wangkai							Java
	chenyanzhe	C++
	everthis						JS
	gaosq0604		Python
	Garvit244		Python
	halfrost								Go
	JoshCrozier						JS
	keineahnung2345	C++
	lennylxx				C
	linouk23	C++
	lkwq007		Python
	luangong	C++
	MacJim	C++
	qiyuangong		Python
	ruoru					Rust
	shreymehul			C#
	suxrobGM			C#
	varunu28							Java
	vli02				C
	wisdompeak	C++
	XiaotaoGuo	C++
	YuriSpiridonov		Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
aylei	Rust
begeekmyfriend	C
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
chenyanzhe	C++
everthis	JavaScript
gaosq0604	Python
Garvit244	Python
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
lennylxx	C
linouk23	C++
lkwq007	Python
luangong	C++
MacJim	C++
qiyuangong	Python
ruoru	Rust
shreymehul	C#
suxrobGM	C#
varunu28	Java
vli02	C
wisdompeak	C++
XiaotaoGuo	C++
YuriSpiridonov	Python
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality