What is the pricing and subscription model for Hi👋SpeedAlgo?

The entire core curriculum of 13 patterns and 225 practice problems is 100% free to access with no credit card required. New accounts get 40 free coins once, the daily claim adds +20 coins once a day, and inviting a friend earns you +25 coins when they complete their first practice step. These are the only ways to earn coins. Each AI coach question costs 1-5 coins, priced by the server according to its size. AI coaching is free with your own Google Gemini, OpenAI or OpenRouter API key (BYOK). Coins also unlock extras for 24 hours: a Recall hint level (1 coin), a Solve solution reveal (2), a LeetCode problem card's solutions (1) and a pattern's extra canonical problems (1). Nothing on the site is sold for money: coins can only be earned, never bought.

What is the refund and cancellation policy?

Hi👋SpeedAlgo sells nothing for money: there are no subscriptions, renewals or charges, so there is nothing to cancel or refund. Nothing on the site is sold for money: coins can only be earned, never bought.

Who creates and maintains the curriculum?

Hi👋SpeedAlgo is developed and maintained by Hi👋WebEnterprise (https://hiwebenterprise.com), an engineering organization focused on developer education, deliberate practice methodologies, and cognitive ergonomics for technical interviews.

How does Hi👋SpeedAlgo prepare candidates for senior and staff SWE interviews?

Rather than rote LeetCode grinding, Hi👋SpeedAlgo uses deliberate practice for each pattern: learn the loop invariant, Big-O proof and edge cases from a side-by-side template and a step-by-step debugger, rebuild the template from memory, then solve a new problem on your own against a graded test suite.

Theory Context•Binary Search Boundary

Builds on Lower Bound, which you haven’t finished yet.

P2MediumBuilt on Lower Bound~4 min speedrun

Search in Rotated Sorted Array

Built on

Lower BoundThe check compares a value with the first value of the list, and it runs twice: once to find the pivot, and once to search the sorted order that starts at the pivot.

The problem

Search in Rotated Sorted Array (LC 33)(opens leetcode.com)

Before: arrange the unique integers from smallest to largest.

Change: the list may stay untouched, or undergo a left rotation. A rotation cuts it at an undisclosed position k (1 <= k < nums.length) and moves the prefix behind the suffix without changing the order inside either piece.

Received: nums contains that final arrangement. A cut at 3 takes the prefix [0, 1, 2] off [0, 1, 2, 4, 5, 6, 7] and places it after [4, 5, 6, 7], giving [4, 5, 6, 7, 0, 1, 2]. An unrotated list is also a valid input.

Locate the integer target in the received list. Report its zero-based index if present; report -1 otherwise. The required running time is O(log n), where n is the length of nums.

Example 1

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

Output:4

0 is at index 4 in the rotated array.

Rotated Array

rotated list ➔ find the pivot with Lower Bound ➔ search the sorted order that starts at the pivot

Spot it when: The statement says a sorted array was rotated by an unknown amount, its values may repeat, and it asks for the index of a target, whether a target exists, or the minimum.

Rotated Array

Python

1	from typing import Callable, List
2
3
4	def binary_search_lower_bound(lo: int, hi: int, is_feasible: Callable[[int], bool]) -> int:
5	"""First candidate in [lo, hi) where is_feasible is True.
6	Precondition: is_feasible is monotonic (False, False, ..., True, True).
7	Returns hi when no candidate is True. N = hi - lo candidates. T = the cost of one is_feasible call.
8	Time: O(T * log N) \| Space: O(1)
9	"""
10	while lo < hi:
11	mid = lo + (hi - lo) // 2
12
13	# 1. Check the Midpoint:
14	# is_feasible(mid) shows which side of the flip mid is on: before the answer (False),
15	# or at the answer or after it (True).
16	if is_feasible(mid):
17	# 2. Keep the Candidate:
18	# mid may be the first True, so keep it in the range by moving hi down to mid.
19	hi = mid
20	else:
21	# 3. Discard the Candidate:
22	# mid is False, so the first True must be strictly to the right of mid.
23	lo = mid + 1
24
25	# 4. Return the Boundary:
26	# The loop stops when lo equals hi; that position is the first True, or hi when none was True.
27	return lo

Invariant: After the trim, nums[i] < nums[0] is False and then True on [0, hi), and nums[(pivot + v) % n] never decreases as v grows from 0 to n - 1.

The first value nums[0] shows which run an index is in, so the check smaller_than_first(i), which is nums[i] < nums[0], is False and then True. The first search returns its first True, the pivot, which is the index where the sorted order starts and holds the smallest value. Read from the pivot, the array is sorted, so map the sorted position v to the index (pivot + v) % n and run Lower Bound again with at_least_target(v). The map visits every index once, from the smallest value to the largest, so at_least_target(v) is also False and then True, and its first True is where target would be. When values repeat, first lower hi while nums[hi - 1] == nums[0]. The trap: when no value is smaller than nums[0], the first search returns hi, which is not an index, so write ... % n and never reset pivot to 0 with if pivot > hi - 1: pivot = 0, because after the trim hi is where the sorted order starts.

See it run

Rotated Array: Lower Bound twice, step by step

lo 0hi 7mid none

The top row is nums by index. The sorted row appears after the pivot is known: position v holds nums[(pivot + v) % n].

lo the first position that can still be the answer
hi the answer is at hi or before it; hi can be one past the end
mid the position the check reads now
lo+mid lo and mid are at the same position
pivot the index where the sorted order starts
pivot+mid mid is at the pivot
answer the first True, where lo and hi meet

nums = [4,5,6,7,0,1,2] and target = 0. The first search finds the pivot, which is the first value smaller than nums[0] = 4.

nums

4lo

endhi

sorted

1 / 9

Gotchas1 of 6

The trap
Gotcha 1: Setting pivot = 0 when no value is smaller
Mistake
```
pivot = binary_search_lower_bound(0, hi, smaller_than_first)
if pivot > hi - 1:
    pivot = 0
```
Fix
```
pivot = binary_search_lower_bound(0, hi, smaller_than_first) % n
```
What happens: When no value in [0, hi) is smaller than nums[0], the first search returns hi. After the trim, hi is where the sorted order starts, so hi % n is the pivot. Resetting the pivot to 0 starts the sorted order in the wrong place. For [0, 1, 0, 0], the trim stops at hi = 2, and the pivot is 2. With a reset to 0, the search for 1 returns -1.
Example: nums = [0, 1, 0, 0], target = 1
Mistake: returns -1Fix: returns 1
Gotcha 2: Forgetting % n in the position map
Mistake
```
return nums[pivot + v] >= target
```
Fix
```
return nums[(pivot + v) % n] >= target
```
What happens: Position v in the sorted order is the index (pivot + v) % n. Without % n, the index goes past the end of the list when pivot + v is at least n. Python raises an IndexError.
Example: nums = [4, 5, 6, 7, 0, 1, 2], target = 0
Mistake: raises IndexErrorFix: returns 4
Gotcha 3: Skipping the trim when values repeat
Mistake
```
hi = n
```
Fix
```
hi = n
while hi > 1 and nums[hi - 1] == nums[0]:
    hi -= 1
```
What happens: Copies of nums[0] at the end of the list look like the first run. Then the check nums[i] < nums[0] is not False and then True, and the pivot search can return a wrong index. For [1, 0, 1, 1, 1], the search for 0 returns -1, and 0 is at index 1.
Example: nums = [1, 0, 1, 1, 1], target = 0
Mistake: returns -1Fix: returns 1
Gotcha 4: Writing <= instead of < in the pivot check
Mistake
```
return nums[i] <= nums[0]
```
Fix
```
return nums[i] < nums[0]
```
What happens: At i = 0, nums[0] <= nums[0] is always True. So the row starts with True and is not False and then True. The first search returns 0, so the pivot is 0 and the second search reads the list as if it were sorted. For [3, 1], the second search finds 3 at position 0, which is not the target 1, so the function returns -1.
Example: nums = [3, 1], target = 1
Mistake: returns -1Fix: returns 1
Gotcha 5: Returning the position without checking the value
Mistake
```
return (pivot + v) % n
```
Fix
```
if v < n and nums[(pivot + v) % n] == target:
    return (pivot + v) % n
return -1
```
What happens: The second search returns the first sorted position whose value is at least target. That value can be larger than target, and v can be n. Without the final check, the function returns an index for a value that is not in the list. For [4, 5, 6, 7, 0, 1, 2] and target = 3, the first True is position 3, which holds 4, so the function returns index 0 instead of -1.
Example: nums = [4, 5, 6, 7, 0, 1, 2], target = 3
Mistake: returns 0Fix: returns -1
Gotcha 6: Reading nums[v] instead of nums[(pivot + v) % n]
Mistake
```
return nums[v] >= target
```
Fix
```
return nums[(pivot + v) % n] >= target
```
What happens: The second check is about sorted positions. Position v is not the index v, unless the list is not rotated. Reading nums[v] asks about the wrong values, the row is not False and then True, and the search returns a wrong answer.
Example: nums = [4, 5, 6, 7, 0, 1, 2], target = 5
Mistake: returns -1Fix: returns 1

Not this one if…

The values climb and then come back down step by step, as in Peak Index in a Mountain Array (LC 852), with no sudden drop from the largest value to the smallest. See Extrema Search
The array is sorted and was not rotated, as in Search Insert Position (LC 35): one Lower Bound search is enough, with no pivot. See Lower Bound

Theory

The question we build

What we know

A rotated sorted array is a sorted array cut once, with the two pieces swapped. With distinct values, the array has two sorted runs. Every value in the first run is at least nums[0]. Every value in the second run is smaller than nums[0]. The pivot is the first index of the second run, and it holds the smallest value.

What the problem gives us

The problem gives nums and target, but not the rotation. So the first search finds the pivot, and the second search uses it.

The question we build

We build two yes-or-no questions on nums = [4, 5, 6, 7, 0, 1, 2] (LeetCode Example 1). The first is: "is nums[i] smaller than nums[0]?" Its first True is the pivot, which is index 4. The second is: "is the value at sorted position v at least target?" Its first True is where target would be. For target = 3, the first True is position 3, which holds 4, not 3. So 3 is not in the list, and the answer is -1.

nums[i]

smaller_than_first(i)

The first True is index 4. nums[4] is 0, the smallest value.

nums[(pivot + v) % n]

at_least_target(v)

target = 3: the first True is position 3, but it holds 4, so 3 is not in the list.

Narrowing down to the template

Both questions are first-True searches, so the template applies to each one. The note Choosing lo and hi, below, gives the two ranges.

Part A: Distinct values

Step 1: Linear scan

A scan reads the values one by one and ignores the sorted order. It is the baseline that the next steps improve.

Step 1: Linear scanPython

1		def search_scan(nums, target):
2		return nums.index(target) if target in nums else -1

Cost: O(N) checks, where N is the number of values.

Step 2: Find the pivot with Lower Bound

Run Lower Bound with the first question. Its first True is the pivot. nums[pivot] is the smallest value, so this step alone answers Find Minimum in Rotated Sorted Array (LC 153). Here the pivot is the index of the smallest value. The statement of Search in Rotated Sorted Array (LC 33) uses the name "pivot index k" for another number: the position in the sorted list where the list was cut. With distinct values, the pivot here is n - k.

Step 2: Find the pivot with Lower BoundPython

1		def find_pivot(nums):
2		n = len(nums)
3
4		def smaller_than_first(i):
5		return nums[i] < nums[0]
6
7		lo = 0
8		hi = n
9		pivot = binary_search_lower_bound(lo, hi, smaller_than_first)
10		return pivot % n # no value is smaller: the array is not rotated, so the pivot is 0

Cost: O(log N) checks.

Step 3: Search the sorted order

A second Lower Bound search runs on the positions 0 to n - 1. It returns only the place where target would be. So the last if checks that the value at that position is target. Without this check, the function returns an index for a value that is not in the list.

Step 3: Search the sorted orderPython

1	+	New line: def search_rotated(nums, target):
2	+	New line: if not nums:
3	+	New line: return -1
4		n = len(nums)
5
6		def smaller_than_first(i):
7		return nums[i] < nums[0]
8
9	+	New line: pivot = binary_search_lower_bound(0, n, smaller_than_first) % n
10
11	+	New line: def at_least_target(v): # v is a position in the sorted order
12	+	New line: return nums[(pivot + v) % n] >= target
13
14	+	New line: v = binary_search_lower_bound(0, n, at_least_target)
15	+	New line: if v < n and nums[(pivot + v) % n] == target:
16	+	New line: return (pivot + v) % n # turn the position back into an index
17	+	New line: return -1

Cost: O(log N) checks for both searches.

Part B: Repeated values

Step 4: Ignore the tail copies of nums[0]

Values at the end of the list that equal nums[0] look like the first run. Then the check nums[i] < nums[0] is no longer False and then True. The trim loop lowers hi past those values before the first search. After the trim, the pivot search runs on [0, hi).

Step 4: Ignore the tail copies of nums[0]Python

1		def search_rotated(nums, target):
2		if not nums:
3		return -1
4		n = len(nums)
5
6	+	New line: hi = n
7	+	New line: while hi > 1 and nums[hi - 1] == nums[0]:
8	+	New line: hi -= 1 # ignore tail copies of nums[0]
9
10		def smaller_than_first(i):
11		return nums[i] < nums[0]
12
13	+	New line: pivot = binary_search_lower_bound(0, hi, smaller_than_first) % n
14
15		def at_least_target(v): # v is a position in the sorted order
16		return nums[(pivot + v) % n] >= target
17
18		v = binary_search_lower_bound(0, n, at_least_target)
19		if v < n and nums[(pivot + v) % n] == target:
20		return (pivot + v) % n # turn the position back into an index
21		return -1

nums[i]

nums[i] < nums[0]

nums = [1, 0, 1, 1, 1] without the trim. The row is not False, then True, so the search cannot find the pivot, which is index 1.

nums[i]

smaller_than_first(i)

With the trim, the range is [0, 2). The row is False, then True, and the first True is index 1.

Cost: O(log N) checks, plus the trim loop. The trim loop runs N - 1 times when every value is equal.

The shorter version

The shorter versionPython

1		import bisect
2
3		def search_rotated_short(nums, target):
4		if not nums:
5		return -1
6		n = len(nums)
7		hi = n
8		while hi > 1 and nums[hi - 1] == nums[0]: # ignore tail copies of nums[0]
9		hi -= 1
10		pivot = bisect.bisect_left(range(hi), True, key=lambda i: nums[i] < nums[0]) % n
11		v = bisect.bisect_left(range(n), True, key=lambda v: nums[(pivot + v) % n] >= target)
12		if v < n and nums[(pivot + v) % n] == target:
13		return (pivot + v) % n
14		return -1

The two bisect_left calls are the two Lower Bound searches. This form needs Python 3.10 or later, because of key=.

Which problems this solves

Problem	Answer
Search in Rotated Sorted Array (LC 33)	`search(nums, target)`: the index, or `-1`.
Search in Rotated Sorted Array II (LC 81)	`search(nums, target) != -1`: `True` or `False`.
Find Minimum in Rotated Sorted Array (LC 153)	`nums[pivot]`: the first search alone.
Find Minimum in Rotated Sorted Array II (LC 154)	`nums[pivot]`, with the trim.

When target appears several times, search returns the first copy in sorted order, reading from the pivot. This can differ from the first copy in the original list. For [1, 1, 0, 1, 1] and target = 1, search returns 3, and nums.index(1) is 0. None of the problems in the table asks for the first copy in the original list.

The cost with repeated values

With distinct values, the cost is O(log N). With repeated values, the trim loop runs N - 1 times when every value is equal, so the cost is O(N). For Search in Rotated Sorted Array II (LC 81), no solution can do better in the worst case. Take a list of N copies of 1 and one 0 at an unknown index, and search for 0. Reading a 1 gives no hint about where the 0 is, so in the worst case every index must be read.

Choosing lo and hi

You look for	Candidates	Call	Nothing is True
The pivot	indices `0 … hi - 1`	`binary_search_lower_bound(0, hi, smaller_than_first)`	`hi`, taken with `% n`: the list is not rotated, or only copies of `nums[0]` were trimmed
The target	positions `0 … n - 1`	`binary_search_lower_bound(0, n, at_least_target)`	`n`: every value is smaller than `target`

Real-world use: a circular log

A fixed-size circular log stores records with a unique, increasing counter. When the log is full, new records overwrite the oldest slots. Read from slot 0, the log is a sorted array that was rotated at the write position. The first search finds the oldest record, which is the pivot. The second search finds a record by its counter. Each search reads about log2(N) values. So the whole search needs about 2 * log2(N) reads, and it works when the log is stored on a slow disk or a remote server. If writers add records while the search runs, the pivot can move between two reads. Then the answer can be wrong. Search a copy of the data, or stop the writers during the search.

Say it in an interview

About 60 seconds, for Search in Rotated Sorted Array (LC 33):

"This is Lower Bound used twice. The check nums[i] < nums[0] is False and then True, and its first True is the pivot, taken modulo n. Read from the pivot, the array is sorted, so the second search runs on the positions v, and position v is index (pivot + v) % n. One last look checks that the value found is target. With repeated values, a trim loop first ignores the values at the end that equal nums[0]. The time is O(log N) with distinct values and O(N) in the worst case with repeated values, and the space is O(1)."

Common Questions

How do you find only the minimum, as in Find Minimum in Rotated Sorted Array (LC 153)?: Run the first search alone. nums[pivot] is the smallest value. With repeated values, run the trim loop first, as in Find Minimum in Rotated Sorted Array II (LC 154).
How do you answer Search in Rotated Sorted Array II (LC 81), which asks only whether target exists?: Return search(nums, target) != -1. The search is the same, and its worst case is O(N).
Why not compare nums[mid] with nums[lo] and nums[hi] in one loop?: That loop works, but it needs several cases and is easy to get wrong at the edges, such as a range of two values. Two Lower Bound searches use one template and one simple check each.

Practice

Canonical LeetCode:Search in Rotated Sorted Array (LC 33)Find Minimum in Rotated Sorted Array (LC 153)Search in Rotated Sorted Array II (LC 81)Find Minimum in Rotated Sorted Array II (LC 154)

Form 1 of 2

Many books teach a rotated list with distinct values as a loop that compares nums[mid] with the last value nums[hi]. That loop finds the minimum, and a second loop finds a target. This course finds the pivot with Lower Bound, and then searches the sorted order that starts at the pivot with Lower Bound again.

The classic loop

Old Way

Python

1	from typing import List
2
3	def find_min_rotated(nums: List[int]) -> int:
4	"""Find Minimum in Rotated Sorted Array: compare `mid` with `hi` to find the break.
5	Time: O(log N) \| Space: O(1)
6	"""
7	lo, hi = 0, len(nums) - 1
8
9	while lo < hi:
10	mid = lo + (hi - lo) // 2
11	if nums[mid] > nums[hi]:
12	lo = mid + 1 # Pivot strictly to the right
13	else:
14	hi = mid # mid itself could be the minimum
15
16	return nums[lo]

From the classic loop to our template

Old Way line	In our template	Why
lo, hi = 0, len(nums) - 1	lo = 0 and hi = n	The classic range is closed, so `hi` is the last index. The template's `hi` is one past the last index.
if nums[mid] > nums[hi]: lo = mid + 1	The new search uses smaller_than_first with the fixed first value	The classic loop compares with the current right endpoint. The new search compares with the fixed first value, `nums[0]`. Their intermediate ranges can differ; both locate a valid start of sorted order.
else: hi = mid	The new search keeps the first True with hi = mid	The template keeps `mid`, because `mid` may be the pivot.
return nums[lo]	pivot = ... % n, and nums[pivot] is the minimum	The classic loop returns the minimum. The pivot is the index of the minimum.

When the classic form is fine

Use it when an interviewer asks for this form, or when the code base already uses it. It finds only the minimum. Finding a target needs a second loop.

Gotchas of the classic loop

Gotchas1 of 3

The trap
Gotcha 1: Comparing nums[mid] with nums[lo] instead of nums[hi]
Mistake
```
if nums[mid] > nums[lo]:
```
Fix
```
if nums[mid] > nums[hi]:
```
What happens: When mid > lo, nums[mid] > nums[lo] is True in an array that is not rotated. There the minimum is on the left. It is also True in the left run of a rotated array. There the minimum is on the right. So the comparison with nums[lo] cannot pick a side. nums[hi] always sits in the right run, so comparing with it tells the two cases apart.
Example: nums = [1, 2, 3, 4, 5] (not rotated)
Mistake: returns 4Fix: returns 1
Gotcha 2: Using this search when values can repeat
What happens: With repeated values, nums[mid] == nums[hi] does not say which run mid is in. The else branch still sets hi = mid. On [1, 1, 1, 0, 1], mid = 2 ties with nums[4]. hi = 2 cuts off the 0 at index 3, and the search returns 1. Find Minimum in Rotated Sorted Array II (LC 154) needs the Rotated Array with Duplicates card, which drops one index on a tie.
Gotcha 3: Testing the sorted half with < instead of <=
Mistake
```
if nums[lo] < nums[mid]:
```
Fix
```
if nums[lo] <= nums[mid]:
```
What happens: Search in Rotated Sorted Array (LC 33) first asks whether the left half nums[lo..mid] is sorted. When lo == mid, the left half is the single value nums[mid], which is sorted. With <, the test says it is not sorted. The search then looks in the wrong half and returns -1.
Example: nums = [3, 1], target = 1
Mistake: returns -1Fix: returns 1

Earlier signals

A sorted array of distinct values was rotated (it has one break), and you need its minimum, the rotation point, or a target inside it.

Earlier invariant

The minimum of nums is always at an index inside [lo, hi].

Earlier direction

rotated / cyclic space ➔ midpoint vs boundary reference ➔ locate pivot

Earlier description

A rotated sorted array is two sorted runs, and every value in the left run is larger than every value in the right run, which always contains nums[hi]. So nums[hi] tells you which run mid is in: if nums[mid] > nums[hi], mid is in the left run and the minimum is strictly to its right, so lo = mid + 1; otherwise mid is in the right run and the minimum is mid or to its left, so hi = mid. Both moves keep the minimum inside [lo, hi], so the loop ends on it; an array that was never rotated is just one run and always takes hi = mid. The trap is comparing with nums[lo] instead: nums[mid] > nums[lo] holds both in an unrotated array (minimum on the left) and in the left run of a rotated one (minimum on the right), so it can't pick a side.

Earlier template

Python

1	from typing import List
2
3	def find_min_rotated(nums: List[int]) -> int:
4	"""Find Minimum in Rotated Sorted Array: compare `mid` with `hi` to find the break.
5	Time: O(log N) \| Space: O(1)
6	"""
7	lo, hi = 0, len(nums) - 1
8
9	while lo < hi:
10	mid = lo + (hi - lo) // 2
11	if nums[mid] > nums[hi]:
12	lo = mid + 1 # Pivot strictly to the right
13	else:
14	hi = mid # mid itself could be the minimum
15
16	return nums[lo]

Earlier gotchas

Comparing nums[mid] with nums[lo] instead of nums[hi]

When mid > lo, nums[mid] > nums[lo] is True in an array that is not rotated. There the minimum is on the left. It is also True in the left run of a rotated array. There the minimum is on the right. So the comparison with nums[lo] cannot pick a side. nums[hi] always sits in the right run, so comparing with it tells the two cases apart.

Using this search when values can repeat

With repeated values, nums[mid] == nums[hi] does not say which run mid is in. The else branch still sets hi = mid. On [1, 1, 1, 0, 1], mid = 2 ties with nums[4]. hi = 2 cuts off the 0 at index 3, and the search returns 1. Find Minimum in Rotated Sorted Array II (LC 154) needs the Rotated Array with Duplicates card, which drops one index on a tie.

Testing the sorted half with < instead of <=

Search in Rotated Sorted Array (LC 33) first asks whether the left half nums[lo..mid] is sorted. When lo == mid, the left half is the single value nums[mid], which is sorted. With <, the test says it is not sorted. The search then looks in the wrong half and returns -1.

Earlier look-alikes

The values climb and then come back down step by step, as in Peak Index in a Mountain Array (LC 852), with no sudden drop from the largest value to the smallest.

Values can repeat, as in Find Minimum in Rotated Sorted Array II (LC 154): nums[mid] == nums[hi] can happen with mid in either run, so the comparison no longer picks a side.

Earlier problems

Find Minimum in Rotated Sorted Array

Search in Rotated Sorted Array

Form 2 of 2

Rotated Array with Duplicates was its own card. Its loop compares nums[mid] with nums[hi], and a tie removes one value from the right end. This course keeps one card and adds one loop before the pivot search: the trim.

The classic loop

Old Way

Python

1	from typing import List
2
3	def find_min_with_duplicates(nums: List[int]) -> int:
4	"""Find Minimum in Rotated Sorted Array II: compare `mid` with `hi`; a tie drops `hi` by one.
5	Time: O(log n) without ties, O(n) worst case \| Space: O(1)
6	"""
7	lo, hi = 0, len(nums) - 1
8
9	while lo < hi: # Stop at one index: it holds the minimum
10	mid = lo + (hi - lo) // 2
11	if nums[mid] > nums[hi]:
12	lo = mid + 1 # mid is in the left run: the minimum is strictly to its right
13	elif nums[mid] < nums[hi]:
14	hi = mid # mid is in the right run: it may be the minimum itself
15	else:
16	hi -= 1 # Tie: the run is unknown, but a copy of nums[hi] stays at mid
17
18	return nums[lo]

From the classic loop to our template

Old Way line	In our template	Why
if nums[mid] > nums[hi]: lo = mid + 1	The new search uses smaller_than_first with the fixed first value	The comparisons use different reference values. Their intermediate ranges can differ; both locate a valid start of sorted order.
elif nums[mid] < nums[hi]: hi = mid	The new search keeps the first True with hi = mid	The template keeps `mid`, because `mid` may be the pivot.
else: hi -= 1	the trim loop before the search	The classic loop removes one tied value from the right end on each pass. The trim removes every copy of `nums[0]` at the end, once, before the search.
return nums[lo]	pivot = ... % n, and nums[pivot] is the minimum	The pivot is the index of the minimum.

When the classic form is fine

Use it when an interviewer asks for this form, or when the code base already uses it. Both forms cost O(N) in the worst case, when every value is equal.

Gotchas of the classic loop

Gotchas1 of 4

The trap
Gotcha 1: Folding the tie into nums[mid] >= nums[hi]
Mistake
```
if nums[mid] >= nums[hi]:
```
Fix
```
if nums[mid] > nums[hi]:
```
What happens: A tie, nums[mid] == nums[hi], does not say which run mid is in. With >=, every tie moves lo = mid + 1. On [3, 1, 3, 3, 3], mid = 2 ties with nums[4]. lo jumps to 3 and skips the 1 at index 1. The tie needs its own branch, hi -= 1.
Example: nums = [3, 1, 3, 3, 3]
Mistake: returns 3Fix: returns 1
Gotcha 2: Writing hi = mid on a tie instead of hi -= 1
Mistake
```
hi = mid
```
Fix
```
hi -= 1
```
What happens: hi = mid is correct when nums[mid] < nums[hi]. On a tie it guesses that the minimum is at mid or to its left. On [1, 1, 1, 0, 1], mid = 2 ties with nums[4]. hi = 2 then cuts off the 0 at index 3. hi -= 1 drops only nums[hi], and a copy of that value stays at mid.
Example: nums = [1, 1, 1, 0, 1]
Mistake: returns 1Fix: returns 0
Gotcha 3: Promising O(log n) when values can repeat
What happens: A tie drops one index, not half of the range. An array of n equal values ties on every pass. So it takes n - 1 passes, which is O(n). The search is O(log n) only when ties are rare.
Gotcha 4: Picking a sorted half when all three ends are equal
What happens: Search in Rotated Sorted Array II (LC 81) has the same tie. When nums[lo] == nums[mid] == nums[hi], neither half can be proven sorted. Shrink both ends with lo += 1 and hi -= 1. This is safe because the line before has already returned when nums[mid] == target. So both ends, which equal nums[mid], are not the target.

Earlier signals

A sorted array that may hold repeated values was rotated, and you need its minimum or must decide whether a target is in it.

Earlier invariant

The minimum value of nums is always held by some index inside [lo, hi].

Earlier description

With repeated values, nums[mid] == nums[hi] no longer tells you which run mid is in: [1, 1, 1, 0, 1] and [1, 0, 1, 1, 1] both tie at mid = 2, yet the minimum is to the right of mid in the first and to the left of it in the second. So a tie cannot halve the range: drop one index with hi -= 1. That is safe because nums[mid] equals nums[hi]: if nums[hi] was the minimum, a copy of it survives at mid, which stays inside [lo, hi]. The two strict cases still halve exactly as in Rotated Array: lo = mid + 1 when nums[mid] > nums[hi], hi = mid when it is smaller. The trap is folding the tie into a strict branch: with if nums[mid] >= nums[hi]: lo = mid + 1, [3, 1, 3, 3, 3] ties at mid = 2 and lo jumps to 3, past the 1 at index 1.

Earlier template

Python

1	from typing import List
2
3	def find_min_with_duplicates(nums: List[int]) -> int:
4	"""Find Minimum in Rotated Sorted Array II: compare `mid` with `hi`; a tie drops `hi` by one.
5	Time: O(log n) without ties, O(n) worst case \| Space: O(1)
6	"""
7	lo, hi = 0, len(nums) - 1
8
9	while lo < hi: # Stop at one index: it holds the minimum
10	mid = lo + (hi - lo) // 2
11	if nums[mid] > nums[hi]:
12	lo = mid + 1 # mid is in the left run: the minimum is strictly to its right
13	elif nums[mid] < nums[hi]:
14	hi = mid # mid is in the right run: it may be the minimum itself
15	else:
16	hi -= 1 # Tie: the run is unknown, but a copy of nums[hi] stays at mid
17
18	return nums[lo]

Earlier gotchas

Folding the tie into nums[mid] >= nums[hi]

A tie, nums[mid] == nums[hi], does not say which run mid is in. With >=, every tie moves lo = mid + 1. On [3, 1, 3, 3, 3], mid = 2 ties with nums[4]. lo jumps to 3 and skips the 1 at index 1. The tie needs its own branch, hi -= 1.

Writing hi = mid on a tie instead of hi -= 1

hi = mid is correct when nums[mid] < nums[hi]. On a tie it guesses that the minimum is at mid or to its left. On [1, 1, 1, 0, 1], mid = 2 ties with nums[4]. hi = 2 then cuts off the 0 at index 3. hi -= 1 drops only nums[hi], and a copy of that value stays at mid.

Promising O(log n) when values can repeat

A tie drops one index, not half of the range. An array of n equal values ties on every pass. So it takes n - 1 passes, which is O(n). The search is O(log n) only when ties are rare.

Picking a sorted half when all three ends are equal

Search in Rotated Sorted Array II (LC 81) has the same tie. When nums[lo] == nums[mid] == nums[hi], neither half can be proven sorted. Shrink both ends with lo += 1 and hi -= 1. This is safe because the line before has already returned when nums[mid] == target. So both ends, which equal nums[mid], are not the target.

Earlier look-alikes

The values are distinct, as in Find Minimum in Rotated Sorted Array (LC 153): nums[mid] equals nums[hi] only when mid == hi, so the O(log n) halving always works and no tie branch is needed.

Earlier problems

Find Minimum in Rotated Sorted Array II

Search in Rotated Sorted Array II

Theory Context•Binary Search Boundary

Builds on Lower Bound, which you haven’t finished yet.

P2MediumBuilt on Lower Bound~4 min speedrun

Search in Rotated Sorted Array

Built on

Lower BoundThe check compares a value with the first value of the list, and it runs twice: once to find the pivot, and once to search the sorted order that starts at the pivot.

The problem

Search in Rotated Sorted Array (LC 33)(opens leetcode.com)

Before: arrange the unique integers from smallest to largest.

Locate the integer target in the received list. Report its zero-based index if present; report -1 otherwise. The required running time is O(log n), where n is the length of nums.

Example 1

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

Output:4

0 is at index 4 in the rotated array.

Rotated Array

rotated list ➔ find the pivot with Lower Bound ➔ search the sorted order that starts at the pivot

Spot it when: The statement says a sorted array was rotated by an unknown amount, its values may repeat, and it asks for the index of a target, whether a target exists, or the minimum.

Rotated Array

Python

1	from typing import Callable, List
2
3
4	def binary_search_lower_bound(lo: int, hi: int, is_feasible: Callable[[int], bool]) -> int:
5	"""First candidate in [lo, hi) where is_feasible is True.
6	Precondition: is_feasible is monotonic (False, False, ..., True, True).
7	Returns hi when no candidate is True. N = hi - lo candidates. T = the cost of one is_feasible call.
8	Time: O(T * log N) \| Space: O(1)
9	"""
10	while lo < hi:
11	mid = lo + (hi - lo) // 2
12
13	# 1. Check the Midpoint:
14	# is_feasible(mid) shows which side of the flip mid is on: before the answer (False),
15	# or at the answer or after it (True).
16	if is_feasible(mid):
17	# 2. Keep the Candidate:
18	# mid may be the first True, so keep it in the range by moving hi down to mid.
19	hi = mid
20	else:
21	# 3. Discard the Candidate:
22	# mid is False, so the first True must be strictly to the right of mid.
23	lo = mid + 1
24
25	# 4. Return the Boundary:
26	# The loop stops when lo equals hi; that position is the first True, or hi when none was True.
27	return lo

Invariant: After the trim, nums[i] < nums[0] is False and then True on [0, hi), and nums[(pivot + v) % n] never decreases as v grows from 0 to n - 1.

See it run

Rotated Array: Lower Bound twice, step by step

lo 0hi 7mid none

The top row is nums by index. The sorted row appears after the pivot is known: position v holds nums[(pivot + v) % n].

lo the first position that can still be the answer
hi the answer is at hi or before it; hi can be one past the end
mid the position the check reads now
lo+mid lo and mid are at the same position
pivot the index where the sorted order starts
pivot+mid mid is at the pivot
answer the first True, where lo and hi meet

nums = [4,5,6,7,0,1,2] and target = 0. The first search finds the pivot, which is the first value smaller than nums[0] = 4.

nums

4lo

endhi

sorted

1 / 9

Gotchas1 of 6

The trap
Gotcha 1: Setting pivot = 0 when no value is smaller
Mistake
```
pivot = binary_search_lower_bound(0, hi, smaller_than_first)
if pivot > hi - 1:
    pivot = 0
```
Fix
```
pivot = binary_search_lower_bound(0, hi, smaller_than_first) % n
```
What happens: When no value in [0, hi) is smaller than nums[0], the first search returns hi. After the trim, hi is where the sorted order starts, so hi % n is the pivot. Resetting the pivot to 0 starts the sorted order in the wrong place. For [0, 1, 0, 0], the trim stops at hi = 2, and the pivot is 2. With a reset to 0, the search for 1 returns -1.
Example: nums = [0, 1, 0, 0], target = 1
Mistake: returns -1Fix: returns 1
Gotcha 2: Forgetting % n in the position map
Mistake
```
return nums[pivot + v] >= target
```
Fix
```
return nums[(pivot + v) % n] >= target
```
What happens: Position v in the sorted order is the index (pivot + v) % n. Without % n, the index goes past the end of the list when pivot + v is at least n. Python raises an IndexError.
Example: nums = [4, 5, 6, 7, 0, 1, 2], target = 0
Mistake: raises IndexErrorFix: returns 4
Gotcha 3: Skipping the trim when values repeat
Mistake
```
hi = n
```
Fix
```
hi = n
while hi > 1 and nums[hi - 1] == nums[0]:
    hi -= 1
```
What happens: Copies of nums[0] at the end of the list look like the first run. Then the check nums[i] < nums[0] is not False and then True, and the pivot search can return a wrong index. For [1, 0, 1, 1, 1], the search for 0 returns -1, and 0 is at index 1.
Example: nums = [1, 0, 1, 1, 1], target = 0
Mistake: returns -1Fix: returns 1
Gotcha 4: Writing <= instead of < in the pivot check
Mistake
```
return nums[i] <= nums[0]
```
Fix
```
return nums[i] < nums[0]
```
What happens: At i = 0, nums[0] <= nums[0] is always True. So the row starts with True and is not False and then True. The first search returns 0, so the pivot is 0 and the second search reads the list as if it were sorted. For [3, 1], the second search finds 3 at position 0, which is not the target 1, so the function returns -1.
Example: nums = [3, 1], target = 1
Mistake: returns -1Fix: returns 1
Gotcha 5: Returning the position without checking the value
Mistake
```
return (pivot + v) % n
```
Fix
```
if v < n and nums[(pivot + v) % n] == target:
    return (pivot + v) % n
return -1
```
What happens: The second search returns the first sorted position whose value is at least target. That value can be larger than target, and v can be n. Without the final check, the function returns an index for a value that is not in the list. For [4, 5, 6, 7, 0, 1, 2] and target = 3, the first True is position 3, which holds 4, so the function returns index 0 instead of -1.
Example: nums = [4, 5, 6, 7, 0, 1, 2], target = 3
Mistake: returns 0Fix: returns -1
Gotcha 6: Reading nums[v] instead of nums[(pivot + v) % n]
Mistake
```
return nums[v] >= target
```
Fix
```
return nums[(pivot + v) % n] >= target
```
What happens: The second check is about sorted positions. Position v is not the index v, unless the list is not rotated. Reading nums[v] asks about the wrong values, the row is not False and then True, and the search returns a wrong answer.
Example: nums = [4, 5, 6, 7, 0, 1, 2], target = 5
Mistake: returns -1Fix: returns 1

Not this one if…

The values climb and then come back down step by step, as in Peak Index in a Mountain Array (LC 852), with no sudden drop from the largest value to the smallest. See Extrema Search
The array is sorted and was not rotated, as in Search Insert Position (LC 35): one Lower Bound search is enough, with no pivot. See Lower Bound

Theory

The question we build

What we know

What the problem gives us

The problem gives nums and target, but not the rotation. So the first search finds the pivot, and the second search uses it.

The question we build

nums[i]

smaller_than_first(i)

The first True is index 4. nums[4] is 0, the smallest value.

nums[(pivot + v) % n]

at_least_target(v)

target = 3: the first True is position 3, but it holds 4, so 3 is not in the list.

Narrowing down to the template

Both questions are first-True searches, so the template applies to each one. The note Choosing lo and hi, below, gives the two ranges.

Part A: Distinct values

Step 1: Linear scan

A scan reads the values one by one and ignores the sorted order. It is the baseline that the next steps improve.

Step 1: Linear scanPython

1		def search_scan(nums, target):
2		return nums.index(target) if target in nums else -1

Cost: O(N) checks, where N is the number of values.

Step 2: Find the pivot with Lower Bound

Step 2: Find the pivot with Lower BoundPython

1		def find_pivot(nums):
2		n = len(nums)
3
4		def smaller_than_first(i):
5		return nums[i] < nums[0]
6
7		lo = 0
8		hi = n
9		pivot = binary_search_lower_bound(lo, hi, smaller_than_first)
10		return pivot % n # no value is smaller: the array is not rotated, so the pivot is 0

Cost: O(log N) checks.

Step 3: Search the sorted order

Step 3: Search the sorted orderPython

1	+	New line: def search_rotated(nums, target):
2	+	New line: if not nums:
3	+	New line: return -1
4		n = len(nums)
5
6		def smaller_than_first(i):
7		return nums[i] < nums[0]
8
9	+	New line: pivot = binary_search_lower_bound(0, n, smaller_than_first) % n
10
11	+	New line: def at_least_target(v): # v is a position in the sorted order
12	+	New line: return nums[(pivot + v) % n] >= target
13
14	+	New line: v = binary_search_lower_bound(0, n, at_least_target)
15	+	New line: if v < n and nums[(pivot + v) % n] == target:
16	+	New line: return (pivot + v) % n # turn the position back into an index
17	+	New line: return -1

Cost: O(log N) checks for both searches.

Part B: Repeated values

Step 4: Ignore the tail copies of nums[0]

Step 4: Ignore the tail copies of nums[0]Python

1		def search_rotated(nums, target):
2		if not nums:
3		return -1
4		n = len(nums)
5
6	+	New line: hi = n
7	+	New line: while hi > 1 and nums[hi - 1] == nums[0]:
8	+	New line: hi -= 1 # ignore tail copies of nums[0]
9
10		def smaller_than_first(i):
11		return nums[i] < nums[0]
12
13	+	New line: pivot = binary_search_lower_bound(0, hi, smaller_than_first) % n
14
15		def at_least_target(v): # v is a position in the sorted order
16		return nums[(pivot + v) % n] >= target
17
18		v = binary_search_lower_bound(0, n, at_least_target)
19		if v < n and nums[(pivot + v) % n] == target:
20		return (pivot + v) % n # turn the position back into an index
21		return -1

nums[i]

nums[i] < nums[0]

nums = [1, 0, 1, 1, 1] without the trim. The row is not False, then True, so the search cannot find the pivot, which is index 1.

nums[i]

smaller_than_first(i)

With the trim, the range is [0, 2). The row is False, then True, and the first True is index 1.

Cost: O(log N) checks, plus the trim loop. The trim loop runs N - 1 times when every value is equal.

The shorter version

The shorter versionPython

1		import bisect
2
3		def search_rotated_short(nums, target):
4		if not nums:
5		return -1
6		n = len(nums)
7		hi = n
8		while hi > 1 and nums[hi - 1] == nums[0]: # ignore tail copies of nums[0]
9		hi -= 1
10		pivot = bisect.bisect_left(range(hi), True, key=lambda i: nums[i] < nums[0]) % n
11		v = bisect.bisect_left(range(n), True, key=lambda v: nums[(pivot + v) % n] >= target)
12		if v < n and nums[(pivot + v) % n] == target:
13		return (pivot + v) % n
14		return -1

The two bisect_left calls are the two Lower Bound searches. This form needs Python 3.10 or later, because of key=.

Which problems this solves

Problem	Answer
Search in Rotated Sorted Array (LC 33)	`search(nums, target)`: the index, or `-1`.
Search in Rotated Sorted Array II (LC 81)	`search(nums, target) != -1`: `True` or `False`.
Find Minimum in Rotated Sorted Array (LC 153)	`nums[pivot]`: the first search alone.
Find Minimum in Rotated Sorted Array II (LC 154)	`nums[pivot]`, with the trim.

The cost with repeated values

Choosing lo and hi

You look for	Candidates	Call	Nothing is True
The pivot	indices `0 … hi - 1`	`binary_search_lower_bound(0, hi, smaller_than_first)`	`hi`, taken with `% n`: the list is not rotated, or only copies of `nums[0]` were trimmed
The target	positions `0 … n - 1`	`binary_search_lower_bound(0, n, at_least_target)`	`n`: every value is smaller than `target`

Real-world use: a circular log

Say it in an interview

About 60 seconds, for Search in Rotated Sorted Array (LC 33):

"This is Lower Bound used twice. The check nums[i] < nums[0] is False and then True, and its first True is the pivot, taken modulo n. Read from the pivot, the array is sorted, so the second search runs on the positions v, and position v is index (pivot + v) % n. One last look checks that the value found is target. With repeated values, a trim loop first ignores the values at the end that equal nums[0]. The time is O(log N) with distinct values and O(N) in the worst case with repeated values, and the space is O(1)."

Common Questions

How do you find only the minimum, as in Find Minimum in Rotated Sorted Array (LC 153)?: Run the first search alone. nums[pivot] is the smallest value. With repeated values, run the trim loop first, as in Find Minimum in Rotated Sorted Array II (LC 154).
How do you answer Search in Rotated Sorted Array II (LC 81), which asks only whether target exists?: Return search(nums, target) != -1. The search is the same, and its worst case is O(N).
Why not compare nums[mid] with nums[lo] and nums[hi] in one loop?: That loop works, but it needs several cases and is easy to get wrong at the edges, such as a range of two values. Two Lower Bound searches use one template and one simple check each.

Practice

Canonical LeetCode:Search in Rotated Sorted Array (LC 33)Find Minimum in Rotated Sorted Array (LC 153)Search in Rotated Sorted Array II (LC 81)Find Minimum in Rotated Sorted Array II (LC 154)

Form 1 of 2

The classic loop

Old Way

Python

1	from typing import List
2
3	def find_min_rotated(nums: List[int]) -> int:
4	"""Find Minimum in Rotated Sorted Array: compare `mid` with `hi` to find the break.
5	Time: O(log N) \| Space: O(1)
6	"""
7	lo, hi = 0, len(nums) - 1
8
9	while lo < hi:
10	mid = lo + (hi - lo) // 2
11	if nums[mid] > nums[hi]:
12	lo = mid + 1 # Pivot strictly to the right
13	else:
14	hi = mid # mid itself could be the minimum
15
16	return nums[lo]

From the classic loop to our template

Old Way line	In our template	Why
lo, hi = 0, len(nums) - 1	lo = 0 and hi = n	The classic range is closed, so `hi` is the last index. The template's `hi` is one past the last index.
if nums[mid] > nums[hi]: lo = mid + 1	The new search uses smaller_than_first with the fixed first value	The classic loop compares with the current right endpoint. The new search compares with the fixed first value, `nums[0]`. Their intermediate ranges can differ; both locate a valid start of sorted order.
else: hi = mid	The new search keeps the first True with hi = mid	The template keeps `mid`, because `mid` may be the pivot.
return nums[lo]	pivot = ... % n, and nums[pivot] is the minimum	The classic loop returns the minimum. The pivot is the index of the minimum.

When the classic form is fine

Use it when an interviewer asks for this form, or when the code base already uses it. It finds only the minimum. Finding a target needs a second loop.

Gotchas of the classic loop

Gotchas1 of 3

The trap
Gotcha 1: Comparing nums[mid] with nums[lo] instead of nums[hi]
Mistake
```
if nums[mid] > nums[lo]:
```
Fix
```
if nums[mid] > nums[hi]:
```
What happens: When mid > lo, nums[mid] > nums[lo] is True in an array that is not rotated. There the minimum is on the left. It is also True in the left run of a rotated array. There the minimum is on the right. So the comparison with nums[lo] cannot pick a side. nums[hi] always sits in the right run, so comparing with it tells the two cases apart.
Example: nums = [1, 2, 3, 4, 5] (not rotated)
Mistake: returns 4Fix: returns 1
Gotcha 2: Using this search when values can repeat
What happens: With repeated values, nums[mid] == nums[hi] does not say which run mid is in. The else branch still sets hi = mid. On [1, 1, 1, 0, 1], mid = 2 ties with nums[4]. hi = 2 cuts off the 0 at index 3, and the search returns 1. Find Minimum in Rotated Sorted Array II (LC 154) needs the Rotated Array with Duplicates card, which drops one index on a tie.
Gotcha 3: Testing the sorted half with < instead of <=
Mistake
```
if nums[lo] < nums[mid]:
```
Fix
```
if nums[lo] <= nums[mid]:
```
What happens: Search in Rotated Sorted Array (LC 33) first asks whether the left half nums[lo..mid] is sorted. When lo == mid, the left half is the single value nums[mid], which is sorted. With <, the test says it is not sorted. The search then looks in the wrong half and returns -1.
Example: nums = [3, 1], target = 1
Mistake: returns -1Fix: returns 1

Earlier signals

A sorted array of distinct values was rotated (it has one break), and you need its minimum, the rotation point, or a target inside it.

Earlier invariant

The minimum of nums is always at an index inside [lo, hi].

Earlier direction

rotated / cyclic space ➔ midpoint vs boundary reference ➔ locate pivot

Earlier description

Earlier template

Python

1	from typing import List
2
3	def find_min_rotated(nums: List[int]) -> int:
4	"""Find Minimum in Rotated Sorted Array: compare `mid` with `hi` to find the break.
5	Time: O(log N) \| Space: O(1)
6	"""
7	lo, hi = 0, len(nums) - 1
8
9	while lo < hi:
10	mid = lo + (hi - lo) // 2
11	if nums[mid] > nums[hi]:
12	lo = mid + 1 # Pivot strictly to the right
13	else:
14	hi = mid # mid itself could be the minimum
15
16	return nums[lo]

Earlier gotchas

Comparing nums[mid] with nums[lo] instead of nums[hi]

Using this search when values can repeat

Testing the sorted half with < instead of <=

Earlier look-alikes

The values climb and then come back down step by step, as in Peak Index in a Mountain Array (LC 852), with no sudden drop from the largest value to the smallest.

Values can repeat, as in Find Minimum in Rotated Sorted Array II (LC 154): nums[mid] == nums[hi] can happen with mid in either run, so the comparison no longer picks a side.

Earlier problems

Find Minimum in Rotated Sorted Array

Search in Rotated Sorted Array

Form 2 of 2

The classic loop

Old Way

Python

1	from typing import List
2
3	def find_min_with_duplicates(nums: List[int]) -> int:
4	"""Find Minimum in Rotated Sorted Array II: compare `mid` with `hi`; a tie drops `hi` by one.
5	Time: O(log n) without ties, O(n) worst case \| Space: O(1)
6	"""
7	lo, hi = 0, len(nums) - 1
8
9	while lo < hi: # Stop at one index: it holds the minimum
10	mid = lo + (hi - lo) // 2
11	if nums[mid] > nums[hi]:
12	lo = mid + 1 # mid is in the left run: the minimum is strictly to its right
13	elif nums[mid] < nums[hi]:
14	hi = mid # mid is in the right run: it may be the minimum itself
15	else:
16	hi -= 1 # Tie: the run is unknown, but a copy of nums[hi] stays at mid
17
18	return nums[lo]

From the classic loop to our template

Old Way line	In our template	Why
if nums[mid] > nums[hi]: lo = mid + 1	The new search uses smaller_than_first with the fixed first value	The comparisons use different reference values. Their intermediate ranges can differ; both locate a valid start of sorted order.
elif nums[mid] < nums[hi]: hi = mid	The new search keeps the first True with hi = mid	The template keeps `mid`, because `mid` may be the pivot.
else: hi -= 1	the trim loop before the search	The classic loop removes one tied value from the right end on each pass. The trim removes every copy of `nums[0]` at the end, once, before the search.
return nums[lo]	pivot = ... % n, and nums[pivot] is the minimum	The pivot is the index of the minimum.

When the classic form is fine

Use it when an interviewer asks for this form, or when the code base already uses it. Both forms cost O(N) in the worst case, when every value is equal.

Gotchas of the classic loop

Gotchas1 of 4

The trap
Gotcha 1: Folding the tie into nums[mid] >= nums[hi]
Mistake
```
if nums[mid] >= nums[hi]:
```
Fix
```
if nums[mid] > nums[hi]:
```
What happens: A tie, nums[mid] == nums[hi], does not say which run mid is in. With >=, every tie moves lo = mid + 1. On [3, 1, 3, 3, 3], mid = 2 ties with nums[4]. lo jumps to 3 and skips the 1 at index 1. The tie needs its own branch, hi -= 1.
Example: nums = [3, 1, 3, 3, 3]
Mistake: returns 3Fix: returns 1
Gotcha 2: Writing hi = mid on a tie instead of hi -= 1
Mistake
```
hi = mid
```
Fix
```
hi -= 1
```
What happens: hi = mid is correct when nums[mid] < nums[hi]. On a tie it guesses that the minimum is at mid or to its left. On [1, 1, 1, 0, 1], mid = 2 ties with nums[4]. hi = 2 then cuts off the 0 at index 3. hi -= 1 drops only nums[hi], and a copy of that value stays at mid.
Example: nums = [1, 1, 1, 0, 1]
Mistake: returns 1Fix: returns 0
Gotcha 3: Promising O(log n) when values can repeat
What happens: A tie drops one index, not half of the range. An array of n equal values ties on every pass. So it takes n - 1 passes, which is O(n). The search is O(log n) only when ties are rare.
Gotcha 4: Picking a sorted half when all three ends are equal
What happens: Search in Rotated Sorted Array II (LC 81) has the same tie. When nums[lo] == nums[mid] == nums[hi], neither half can be proven sorted. Shrink both ends with lo += 1 and hi -= 1. This is safe because the line before has already returned when nums[mid] == target. So both ends, which equal nums[mid], are not the target.

Earlier signals

A sorted array that may hold repeated values was rotated, and you need its minimum or must decide whether a target is in it.

Earlier invariant

The minimum value of nums is always held by some index inside [lo, hi].

Earlier description

Earlier template

Python

1	from typing import List
2
3	def find_min_with_duplicates(nums: List[int]) -> int:
4	"""Find Minimum in Rotated Sorted Array II: compare `mid` with `hi`; a tie drops `hi` by one.
5	Time: O(log n) without ties, O(n) worst case \| Space: O(1)
6	"""
7	lo, hi = 0, len(nums) - 1
8
9	while lo < hi: # Stop at one index: it holds the minimum
10	mid = lo + (hi - lo) // 2
11	if nums[mid] > nums[hi]:
12	lo = mid + 1 # mid is in the left run: the minimum is strictly to its right
13	elif nums[mid] < nums[hi]:
14	hi = mid # mid is in the right run: it may be the minimum itself
15	else:
16	hi -= 1 # Tie: the run is unknown, but a copy of nums[hi] stays at mid
17
18	return nums[lo]

Earlier gotchas

Folding the tie into nums[mid] >= nums[hi]

Writing hi = mid on a tie instead of hi -= 1

Promising O(log n) when values can repeat

A tie drops one index, not half of the range. An array of n equal values ties on every pass. So it takes n - 1 passes, which is O(n). The search is O(log n) only when ties are rare.

Picking a sorted half when all three ends are equal

Earlier look-alikes

The values are distinct, as in Find Minimum in Rotated Sorted Array (LC 153): nums[mid] equals nums[hi] only when mid == hi, so the O(log n) halving always works and no tie branch is needed.

Earlier problems

Find Minimum in Rotated Sorted Array II

Search in Rotated Sorted Array II