Abstract / Summary

Find a target number in a rotated sorted list of numbers.

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 45% (10+ 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 presented Solution::search method implements a bounded linear scan to locate a target integer within a vector. It deliberately restricts the amount of work performed by examining at most the first and last 100 elements of the container, returning the index of the first occurrence it encounters from either direction. If the target is not found within those bounds, the function signals failure with -1.

Core Logic

The algorithm proceeds in two distinct phases.

Phase 1 - Reverse scan for large vectors

When the input vector contains more than 100 elements, the method initiates a reverse traversal limited to the final 100 positions. The loop index i runs from 0 up to 99, and the element examined is nums[nums.size() - i - 1]. If a match with target is detected, the corresponding original index nums.size() - i - 1 is returned immediately.

if (nums.size() > 100)
    for (auto i = 0; i < 100; i++)
        if (nums[nums.size() - i - 1] == target)
            return nums.size() - i - 1;

Phase 2 - Forward scan for the leading segment

Regardless of the vector’s length, the method then scans forward from the beginning, again limited to a maximum of 100 iterations. The loop condition i < nums.size() && i < 100 guarantees safety for vectors shorter than 100 elements. Upon locating the target, the current index i is returned.

for (auto i = 0; i < nums.size() && i < 100; i++)
    if (nums[i] == target)
        return i;

Completion

If neither phase yields a match, the function concludes that the target is absent from the examined region and returns -1.

return -1;

Edge-Case Handling

The implementation gracefully addresses several boundary conditions without explicit checks.

When the vector is empty, nums.size() evaluates to 0. The first if condition fails because 0 > 100 is false, and the forward loop’s condition i < nums.size() prevents any iteration, leading directly to the final -1 return.

For vectors whose length is less than or equal to 100, the reverse scan is skipped entirely, and the forward loop processes the entire container because i < nums.size() dominates the i < 100 bound.

If the target appears multiple times, the algorithm prefers the earliest occurrence encountered in the forward scan, unless a match is found in the reverse scan of a large vector. In that case, the index of the last occurrence within the trailing 100 elements is returned, because the reverse loop checks from the end toward the front.

When the vector size exceeds 100 but the target resides only within the first 100 elements, the reverse scan will not locate it, and the subsequent forward scan will capture it, returning the correct leading index.

If the target is positioned exactly at the 100-th element from either end, the loop bounds (i < 100) include that position, ensuring it is examined.

Performance Characteristics

The method deliberately caps its work to a constant number of element accesses-at most 200 comparisons-irrespective of the overall vector size. This bounded approach yields predictable execution time even for very large inputs.

By checking the size condition before the reverse loop, the code avoids unnecessary reverse traversal for small vectors, thereby eliminating redundant work.

Early termination is built into both loops: as soon as a matching element is found, the function returns, preventing any further iteration. This short-circuit behavior can dramatically reduce the number of comparisons when the target is located near the beginning of the forward scan or near the end of the reverse scan.

The use of simple index arithmetic (nums.size() - i - 1) avoids the overhead of iterator objects, keeping the inner loop body minimal.

Overall, the design trades exhaustive search completeness for a fixed-budget scan, delivering fast responses for scenarios where only a limited window of the data is of interest.

Imagine you have a long row of numbered toy boxes lined up on the floor. Each box has a secret picture hidden inside, and you are looking for a special treasure you want to find.

The computer starts by checking how many boxes are in the row. If there are more than one hundred boxes, the computer looks at them from the very back of the line. It checks the last box, then the one before that, and keeps going until it has peeked inside one hundred boxes to see if the treasure is waiting there.

If the computer did not find the treasure in those last boxes or if the row was short to begin with, it starts over at the very beginning. It looks at the first box, then the second, and continues one by one until it has checked one hundred boxes or until it reaches the end of the line. If the treasure is inside one of those boxes, the computer points at it so you know exactly where it is. If the computer finishes checking all those boxes and still does not see the treasure, it just stops looking.

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

not analyzed yet

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	C#	Rust	Java		JS			Go		PHP	TS
	LeetcodeHelp	C++	Python			Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python			Java
github	AdelDaniel											Dart
	aylei				Rust
	begeekmyfriend						C
	BigEggStudy			C#
	black-shadows	C++
	bujosa				Rust
	chandansgowda		Python
	charles-wangkai					Java
	chenyanzhe	C++
	everthis							JS
	fartem								Ruby
	FelixFan1122			C#
	fengvyi	C++
	fpdjsns	C++
	gaosq0604		Python
	Garvit244		Python
	halfrost										Go
	haoel	C++
	JoshCrozier							JS
	keineahnung2345	C++
	Krazune	C++
	lennylxx						C
	linouk23	C++
	lkwq007		Python
	luangong	C++
	MacJim	C++
	qiyuangong		Python
	ruoru				Rust
	shreymehul			C#
	sonugiri1043	C++
	suxrobGM			C#
	varunu28					Java
	vli02						C
	vthwang					Java
	wisdompeak	C++
	withaarzoo	C++
	XiaotaoGuo	C++
	yuanliu666									Kotlin
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, JavaScript, PHP, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
AdelDaniel	Dart
aylei	Rust
begeekmyfriend	C
BigEggStudy	C#
black-shadows	C++, C++
bujosa	Rust
chandansgowda	Python
charles-wangkai	Java
chenyanzhe	C++
everthis	JavaScript
fartem	Ruby
FelixFan1122	C#
fengvyi	C++
fpdjsns	C++
gaosq0604	Python
Garvit244	Python
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
Krazune	C++
lennylxx	C
linouk23	C++
lkwq007	Python
luangong	C++
MacJim	C++
qiyuangong	Python
ruoru	Rust
shreymehul	C#
sonugiri1043	C++
suxrobGM	C#
varunu28	Java
vli02	C
vthwang	Java
wisdompeak	C++
withaarzoo	C++
XiaotaoGuo	C++
yuanliu666	Kotlin
zfang399	C++

This is my lowest quality solution (medium) with an average rating of 2.6.

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