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.

P1MediumMental model~4 min speedrun

Upper Bound (Last True Binary Search)

Unlocks

Feasible Function Ordered Set

The problem

Sqrt(x) (LC 69)(opens leetcode.com)

Take a whole number x that is 0 or more. Find the largest whole number whose square is at most x: the square root of x with any fractional part thrown away. For x = 8, whose real root is about 2.83, that number is 2.

The problem forbids letting a built-in exponent function or operator do the work, so something like x ** 0.5 in Python or pow(x, 0.5) in C++ is not allowed.

Example 1

Input:x = 4

Output:2

2 * 2 = 4 fits exactly and 3 * 3 = 9 is too big, so the answer is 2.

k * k <= 4

Upper Bound

candidate domain ➔ monotonic boolean sequence [T, T, ..., F, F] ➔ last True

Spot it when: The statement asks for the largest value that still passes a test, or the last position that is at most a limit, such as the integer square root of x (Sqrt(x) (LC 69)) or the latest timestamp that is not after a given time (Time Based Key-Value Store (LC 981)).

Upper Bound

Python

1	from typing import Callable
2
3
4	def binary_search_upper_bound(lo: int, hi: int, is_feasible: Callable[[int], bool]) -> int:
5	"""Last candidate in [lo, hi) where is_feasible is True; lo - 1 when none is True."""
6	# lo becomes a known True, or the sentinel one before the first candidate; hi becomes the last candidate.
7	lo, hi = lo - 1, hi - 1
8
9	while lo < hi:
10	# 1. Compute the Ceiling Midpoint:
11	# Round mid up so lo < mid <= hi; rounding down would leave mid stuck at lo when one candidate remains.
12	mid = lo + (hi - lo + 1) // 2
13
14	# 2. Check the Midpoint:
15	# is_feasible(mid) shows which side of the flip mid is on: True at mid or before it, or False after it.
16	if is_feasible(mid):
17	# 3. Keep the Candidate:
18	# mid may be the last True, so keep it in the range by moving lo up to mid.
19	lo = mid
20	else:
21	# 4. Discard the Candidate:
22	# mid is False, so the last True must be strictly to the left of mid.
23	hi = mid - 1
24
25	# 5. Return the Boundary:
26	# The loop stops when lo equals hi; that position is the last True, or the sentinel when none was True.
27	return lo

Invariant: Every candidate up to lo is True, or lo is the sentinel just before the first candidate, and every candidate above hi is False, so the last True is always in [lo, hi].

The check reads True…True False…False and the answer is the last True, so a True mid must stay in the range with lo = mid, and a False mid is dropped with hi = mid - 1. lo = mid can leave lo where it was, so the midpoint rounds up with mid = lo + (hi - lo + 1) // 2, which gives lo < mid <= hi. Then lo = mid always moves lo forward. The template first shifts both bounds down by 1 with lo, hi = lo - 1, hi - 1. After the shift, lo starts at the sentinel, which is the position lo - 1 just before the first candidate, and later holds a candidate that passed the check. hi starts at the last candidate. The sentinel is the value that the call returns when no candidate is True. The last True stays in [lo, hi] after both moves, and each move makes the range smaller, so the loop stops with lo == hi and returns lo. The trap is the rounded-down midpoint lo + (hi - lo) // 2 together with lo = mid. When hi == lo + 1, mid equals lo, a True check leaves lo where it was, and the loop never ends.

See it run

Upper Bound, step by step

lo -1hi 8mid -

Each column is one candidate k. T means True and F means False. The first column is the sentinel before the first candidate, and it is never tested.

lo the left end of the range. It is a known True, or the sentinel.
hi the right end of the range. Every candidate after hi is False.
mid the candidate that this pass tests. It is rounded up.
mid = hi mid and hi are the same candidate
answer the last True, or the sentinel when no candidate is True

Start: the range [0, 9) is shifted down by 1, so lo = -1 and hi = 8. lo = -1 is the sentinel before the first candidate.

nonelo

8hi

fits(k)

1 / 10

Gotchas1 of 7

The trap
Gotcha 1: Using the round-down midpoint with lo = mid
Mistake
```
mid = lo + (hi - lo) // 2
```
Fix
```
mid = lo + (hi - lo + 1) // 2
```
What happens: When two possible answers are left (lo and hi, with hi == lo + 1), lo + (hi - lo) // 2 is equal to lo. If the check is True there, lo = mid leaves lo where it was. The range does not become smaller, and the loop never ends. The round-up midpoint is always larger than lo.
Example: Sqrt(x) (LC 69): x = 8
Mistake: the loop never endsFix: returns 2
Gotcha 2: Writing hi = mid instead of hi = mid - 1
Mistake
```
hi = mid
```
Fix
```
hi = mid - 1
```
What happens: The round-up midpoint can be equal to hi. If the check is False there, hi = mid leaves hi where it was. The range does not become smaller, and the loop never ends. For a = [1, 2, 2, 3] and x = 2, the last pass has lo = 2 and hi = 3. Then mid is 3, the check a[3] <= 2 is False, and hi stays 3.
Example: a = [1, 2, 2, 3], x = 2
Mistake: the loop never endsFix: returns 2
Gotcha 3: Not shifting hi down by 1
Mistake
```
lo, hi = lo - 1, hi
```
Fix
```
lo, hi = lo - 1, hi - 1
```
What happens: The template moves hi down by 1 so that hi is the last candidate. Without the shift, hi is one past the last candidate. The round-up midpoint can then be equal to hi, and the check is called with a position that is not a candidate. For a = [5, 6, 7] and a check that is always True, the loop calls the check with index 3, and a[3] raises an IndexError.
Example: a = [5, 6, 7], and every value passes the check a[i] < 10
Mistake: raises IndexErrorFix: returns 2
Gotcha 4: Using Lower Bound's check nums[i] >= target
Mistake
```
is_feasible = lambda i: nums[i] >= target
```
Fix
```
is_feasible = lambda i: nums[i] <= target
```
What happens: Upper Bound needs a check that reads True…True False…False. nums[i] >= target reads False…False True…True, which is the row for Lower Bound. The search then follows the wrong side. For nums = [1, 3, 5, 6] and target = 3, the check is True from index 1 on, so every probe passes, the search keeps moving right, and it returns 3. The last index with nums[i] <= 3 is 1.
Example: nums = [1, 3, 5, 6], target = 3
Mistake: returns 3Fix: returns 1
Gotcha 5: Using the answer as an index without checking it
Mistake
```
value = a[answer]
```
Fix
```
value = a[answer] if answer >= 0 else None
```
What happens: When no candidate is True, the answer is -1. In Python, a[-1] does not raise an error. It reads the last value of the list, and the code continues with a wrong value. Check answer >= 0 before you read a[answer].
Example: a = [5, 6, 7], x = 3: no value is at most 3
Mistake: returns 7Fix: returns None
Gotcha 6: Using the last True index as a count
Mistake
```
count = last_index
```
Fix
```
count = last_index + 1
```
What happens: Indices start at 0. So the number of values up to the last True index is that index plus 1. For a = [1, 2, 2, 3] and x = 2, the last index with a[i] <= 2 is 2, and the count is 3.
Example: a = [1, 2, 2, 3], x = 2
Mistake: returns 2Fix: returns 3
Gotcha 7: Expecting bisect_right to find the last True
Mistake
```
last = bisect.bisect_right(a, x)
```
Fix
```
last = bisect.bisect_right(a, x) - 1
```
What happens: bisect_right finds the first index where a[i] > x. That is a first True, not a last True. For a = [1, 2, 2, 3] and x = 2, it returns 3. The last index with a[i] <= 2 is 2, so subtract 1.
Example: a = [1, 2, 2, 3], x = 2
Mistake: returns 3Fix: returns 2

Not this one if…

You need the first value where a check turns True, the smallest letter greater than target, as in Find Smallest Letter Greater Than Target (LC 744). See Lower Bound
You only need to know whether some integer squares to exactly num, as in Valid Perfect Square (LC 367): a three-way compare can stop the moment mid * mid == num, with no boundary to find. See Exact Match
There is no formula or index to test: checking one guess means placing every ball greedily across the whole input, as in Magnetic Force Between Two Balls (LC 1552), so building that check is the real work. See Feasible Function

Theory

The question we build

What we know

A candidate is a possible answer, here a whole number k. The square k * k only gets larger when k gets larger, so the check k * k <= x is True for small k and False from some k on.

What the problem gives us

The input is x. The candidates are the whole numbers 0 to x, and the answer is the last candidate that passes the check fits.

The question we build

For x = 8, the checks for k = 0 to 8 read True, True, True, False, False, False, False, False, False. The last True is k = 2.

fits(k)

The last True is k = 2, because 2 * 2 = 4 is at most 8 and 3 * 3 = 9 is not.

Narrowing down to the template

The candidates are 0 to x, so the call is binary_search_upper_bound(0, x + 1, fits). Here hi = x + 1 is one past the last candidate, as in Lower Bound.

Step 1: Linear scan

Start at lo - 1, the position just before the first candidate. Move forward while the next candidate passes. The position where the scan stops is the last True.

Step 1: Linear scanPython

1		def last_true_scan(lo, hi, is_feasible):
2		last = lo - 1
3		while last + 1 < hi and is_feasible(last + 1):
4		last += 1
5		return last

Cost: O(N) checks for N candidates.

Step 2: Keep the last True

The scan checks the candidates in order. The halving loop checks only mid, and each check removes one side of the range. The table shows which parts mirror Lower Bound.

Step 2: Keep the last TruePython

1		def binary_search_upper_bound(lo: int, hi: int, is_feasible: Callable[[int], bool]) -> int:
2		"""Last candidate in [lo, hi) where is_feasible is True; lo - 1 when none is True."""
3		# lo becomes a known True, or the sentinel one before the first candidate; hi becomes the last candidate.
4		lo, hi = lo - 1, hi - 1
5
6		while lo < hi:
7		# 1. Compute the Ceiling Midpoint:
8		# Round mid up so lo < mid <= hi; rounding down would leave mid stuck at lo when one candidate remains.
9		mid = lo + (hi - lo + 1) // 2
10
11		# 2. Check the Midpoint:
12		# is_feasible(mid) shows which side of the flip mid is on: True at mid or before it, or False after it.
13		if is_feasible(mid):
14		# 3. Keep the Candidate:
15		# mid may be the last True, so keep it in the range by moving lo up to mid.
16		lo = mid
17		else:
18		# 4. Discard the Candidate:
19		# mid is False, so the last True must be strictly to the left of mid.
20		hi = mid - 1
21
22		# 5. Return the Boundary:
23		# The loop stops when lo equals hi; that position is the last True, or the sentinel when none was True.
24		return lo

Cost: O(T * log(N + 1)) time and O(1) space, where T is the cost of one check.

Item	Lower Bound	Upper Bound
Row	`False then True`	`True then False`
Internal bounds	`[lo, hi)`	`[lo - 1, hi - 1]`, including the sentinel
Midpoint	Floor	Ceiling: `lo < mid <= hi`
Passing check	`hi = mid`	`lo = mid`
Failing check	`lo = mid + 1`	`hi = mid - 1`

The shorter version

1. A range of candidates, range(lo, hi)

Python's bisect_right cannot take this card's check directly for a range of integer candidates. It needs the opposite check, not fits(k), and its result is a position that must be converted back to a candidate. These two steps make the code harder to read than this card's template. For integer candidates, call binary_search_upper_bound.

2. A sorted list, nums

2. A sorted list, numsPython

1		from bisect import bisect_right
2
3		# nums is sorted; insertion position after values <= target, minus 1.
4		last = bisect_right(nums, target, lo, hi) - 1
5		value = nums[last] if last >= lo else None
6
7		# Records are sorted by their numeric first field.
8		records = [(1, 'Ada'), (2, 'Bo'), (2, 'Cy'), (4, 'Di')]
9		last_record = bisect_right(records, 2, 1, 4, key=lambda record: record[0]) - 1 # 2

bisect_right(nums, target, lo, hi) returns the insert position after all values equal to target. Subtract 1 to get the last index in [lo, hi) where nums[i] <= target. The position is already an index in nums, so do not add lo. For nums = [1, 2, 2, 2, 4], target = 2, lo = 2 and hi = 5, bisect returns 4, and the last qualifying index is 3. When no value qualifies, the result is lo - 1, so check last >= lo before you index. Use 0 <= lo <= hi <= len(nums).

For records, key=lambda record: record[0] reads the numeric field, and the records must already be sorted by that field. Bisect applies the key to the records and not to the target, so the target 2 is already a number. The bounds 1, 4 search the records at indices 1, 2 and 3. bisect_right returns 3, after the records with key 2, and 3 - 1 = 2 is the last record whose key is at most 2. When no record qualifies, the result is 0, one before this window. The key= argument needs Python 3.10 or later.

How to build is_feasible

Ask the same four questions as for Lower Bound, in this order:

Does this value still fit? Name it in words, for example fits.
Is the row True…True False…False? Draw the row on a tiny input. If the row has another shape, the check is wrong.
Can I evaluate the check for one proposed candidate using the input? State the work one evaluation performs. It may read neighbours, count values, or simulate a process.
What range [lo, hi) holds every possible answer? hi is one past the last candidate.

Lower Bound and Upper Bound need different checks. Lower Bound's row reads False…False True…True, for example nums[i] >= target. Upper Bound's row reads True…True False…False, for example nums[i] <= target. The two checks are not opposites, because an equal value passes both. For nums = [1, 2, 2, 2, 4] and target = 2, nums[i] >= target gives the first equal index, 1, and nums[i] <= target gives the last equal index, 3.

Here are two worked checks, each drawn on a tiny input.

k * (k + 1) // 2 <= n

Arranging Coins (LC 441) with n = 5. A staircase with k full rows needs k * (k + 1) // 2 coins. The candidates are 0 to n, so hi = n + 1 = 6.

a[i]

a[i] <= x

The last index with a[i] <= 2 in [1, 2, 2, 3] is 2.

Choosing lo and hi

[lo, hi) is the same half-open range as in Lower Bound. lo is a candidate, and hi is one past the last candidate. The last column is what the call returns when no candidate is True, for lo = 0.

You look for	Candidates	Call	Nothing is True
The last index with `a[i] <= x`	indices `0 … len - 1`	`binary_search_upper_bound(0, len(a), check)`	`-1`, which means no such index
The largest `k` with `k * k <= x`	values `0 … x`	`binary_search_upper_bound(0, x + 1, check)`	`-1` (this never happens for Sqrt(x), because `k = 0` always fits)

Put every candidate that can be the answer inside [lo, hi). The answer lo - 1 for "nothing is True" is outside the range, on purpose. Decide what the call returns when no candidate passes, and check that the template gives that value.

The contract

Item	Upper Bound
Range	Half-open `[lo, hi)`, the same as Lower Bound.
The check	Takes one candidate. Returns `True` or `False`. Must be True…True False…False over `[lo, hi)`.
Returns	The last True.
No candidate is True	`lo - 1` of the original call.
Every candidate is True	`hi - 1` of the original call, which is the last candidate.
Cost	`O(T * log N)` time and `O(1)` space. `N = hi - lo`, and `T` is the cost of one check.

For Sqrt(x) (LC 69), mySqrt(0) is 0 and mySqrt(1) is 1, because k = 0 always fits.

The midpoint is lo + (hi - lo + 1) // 2. It gives the same number as (lo + hi + 1) // 2. In Java, C++ and C#, lo + hi + 1 can be larger than the largest 32-bit integer, and the result then becomes negative. lo + (hi - lo + 1) // 2 never goes above hi, so it is safe in every language. Python integers have no limit.

Insertion positions: last True and counts

Take a = [1, 2, 2, 2, 4] and x = 2. The equal values occupy the indices 1 to 3.

Question	Our helper	Python
First index with `a[i] >= x`	`binary_search_lower_bound(0, len(a), lambda i: a[i] >= x)` gives 1	`bisect_left(a, x)` gives 1
Last index with `a[i] <= x`	`binary_search_upper_bound(0, len(a), lambda i: a[i] <= x)` gives 3	`bisect_right(a, x) - 1` gives 3
Position after all values `<= x`	Upper Bound result + 1 gives 4	`bisect_right(a, x)` gives 4

bisect_left puts the position before the equal values. bisect_right puts it after them. Our Upper Bound returns the last passing candidate, which is one position before bisect_right.

For a window, pass lo and hi. The returned position is an index in the whole list, not an offset in the window.

Code / Blueprint

left = bisect_left(nums, target, lo, hi)
right = bisect_right(nums, target, lo, hi)

Values in nums[lo:hi]	Count
< target	left - lo
<= target	right - lo
== target	right - left
> target	hi - right
>= target	hi - left

For nums = [1, 2, 2, 2, 4], target = 2, lo = 2 and hi = 5, left is 2 and right is 4. Two values in the window are at most 2, and both equal 2. Using right alone would also count the values before the window.

Overflow in the square-root check

The check for mySqrt is k * k <= x. The check multiplies k by itself, so it can overflow in a language with fixed-width integers.

LeetCode limits x to at most 2³¹ - 1 for Sqrt(x) (LC 69). The first probe is about x / 2, which is about 2³⁰. Then k * k is about 2⁶⁰. That is much larger than a 32-bit integer can hold, and it fits in a 64-bit integer. In Java, C# or C++, compute k * k in a 64-bit type. You can also avoid the multiplication and compare k == 0 or k <= x // k. For k >= 1 this gives the same answer as k * k <= x, and k = 0 always fits. Python integers have no fixed width, so this risk does not apply in Python.

A different mistake is a floating-point shortcut such as int(x ** 0.5) or int(math.sqrt(x)). It returns the exact answer for every 32-bit input. A 64-bit floating-point number holds only 53 bits of precision, so for a 64-bit input the result can be one away from the true answer. Exact integer code, such as this card's check, never has that risk.

Real-world use

Python's standard library has exactly this function: math.isqrt(n) returns the integer square root rounded down. Use it when a floating-point number must not decide the answer, for example when you test whether an integer is a perfect square.

Say it in an interview

About 60 seconds, for Sqrt(x) (LC 69):

"I use Upper Bound to find the largest k whose square is at most x, because the check reads True, then False. I pass [0, x + 1), and the template shifts both bounds down by 1. The midpoint rounds up, so lo < mid <= hi. A passing mid becomes lo, and a failing mid makes hi = mid - 1. The loop returns lo when lo == hi, in O(log(x + 1)) time and O(1) space. The trap is the rounded-down midpoint, which leaves lo = mid stuck when hi == lo + 1."

Common Questions

How do you get the last True with Lower Bound instead?: Ask for the first index where the opposite check is True, then subtract 1. For Sqrt(x) (LC 69), binary_search_lower_bound(0, x + 1, lambda k: k * k > x) - 1 gives the same answer as Upper Bound, including x = 0 and x = 1. Upper Bound avoids the opposite check and the subtraction.
How do the two cards solve Find First and Last Position of Element in Sorted Array (LC 34)?: The first position is Lower Bound with nums[i] >= target. The last position is Upper Bound with nums[i] <= target. The target is present only when the first position is not after the last position. Otherwise the answer is [-1, -1]. For nums = [1, 2, 2, 2, 4] and target = 2, the positions are 1 and 3.

Practice

Canonical LeetCode:Sqrt(x) (LC 69)Arranging Coins (LC 441)Find First and Last Position of Element in Sorted Array (LC 34)Time Based Key-Value Store (LC 981)

Theory Context•Binary Search Boundary

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

P1MediumMental model~4 min speedrun

Upper Bound (Last True Binary Search)

Unlocks

Feasible Function Ordered Set

The problem

Sqrt(x) (LC 69)(opens leetcode.com)

The problem forbids letting a built-in exponent function or operator do the work, so something like x ** 0.5 in Python or pow(x, 0.5) in C++ is not allowed.

Example 1

Input:x = 4

Output:2

2 * 2 = 4 fits exactly and 3 * 3 = 9 is too big, so the answer is 2.

k * k <= 4

Upper Bound

candidate domain ➔ monotonic boolean sequence [T, T, ..., F, F] ➔ last True

Upper Bound

Python

1	from typing import Callable
2
3
4	def binary_search_upper_bound(lo: int, hi: int, is_feasible: Callable[[int], bool]) -> int:
5	"""Last candidate in [lo, hi) where is_feasible is True; lo - 1 when none is True."""
6	# lo becomes a known True, or the sentinel one before the first candidate; hi becomes the last candidate.
7	lo, hi = lo - 1, hi - 1
8
9	while lo < hi:
10	# 1. Compute the Ceiling Midpoint:
11	# Round mid up so lo < mid <= hi; rounding down would leave mid stuck at lo when one candidate remains.
12	mid = lo + (hi - lo + 1) // 2
13
14	# 2. Check the Midpoint:
15	# is_feasible(mid) shows which side of the flip mid is on: True at mid or before it, or False after it.
16	if is_feasible(mid):
17	# 3. Keep the Candidate:
18	# mid may be the last True, so keep it in the range by moving lo up to mid.
19	lo = mid
20	else:
21	# 4. Discard the Candidate:
22	# mid is False, so the last True must be strictly to the left of mid.
23	hi = mid - 1
24
25	# 5. Return the Boundary:
26	# The loop stops when lo equals hi; that position is the last True, or the sentinel when none was True.
27	return lo

Invariant: Every candidate up to lo is True, or lo is the sentinel just before the first candidate, and every candidate above hi is False, so the last True is always in [lo, hi].

See it run

Upper Bound, step by step

lo -1hi 8mid -

Each column is one candidate k. T means True and F means False. The first column is the sentinel before the first candidate, and it is never tested.

lo the left end of the range. It is a known True, or the sentinel.
hi the right end of the range. Every candidate after hi is False.
mid the candidate that this pass tests. It is rounded up.
mid = hi mid and hi are the same candidate
answer the last True, or the sentinel when no candidate is True

Start: the range [0, 9) is shifted down by 1, so lo = -1 and hi = 8. lo = -1 is the sentinel before the first candidate.

nonelo

8hi

fits(k)

1 / 10

Gotchas1 of 7

The trap
Gotcha 1: Using the round-down midpoint with lo = mid
Mistake
```
mid = lo + (hi - lo) // 2
```
Fix
```
mid = lo + (hi - lo + 1) // 2
```
What happens: When two possible answers are left (lo and hi, with hi == lo + 1), lo + (hi - lo) // 2 is equal to lo. If the check is True there, lo = mid leaves lo where it was. The range does not become smaller, and the loop never ends. The round-up midpoint is always larger than lo.
Example: Sqrt(x) (LC 69): x = 8
Mistake: the loop never endsFix: returns 2
Gotcha 2: Writing hi = mid instead of hi = mid - 1
Mistake
```
hi = mid
```
Fix
```
hi = mid - 1
```
What happens: The round-up midpoint can be equal to hi. If the check is False there, hi = mid leaves hi where it was. The range does not become smaller, and the loop never ends. For a = [1, 2, 2, 3] and x = 2, the last pass has lo = 2 and hi = 3. Then mid is 3, the check a[3] <= 2 is False, and hi stays 3.
Example: a = [1, 2, 2, 3], x = 2
Mistake: the loop never endsFix: returns 2
Gotcha 3: Not shifting hi down by 1
Mistake
```
lo, hi = lo - 1, hi
```
Fix
```
lo, hi = lo - 1, hi - 1
```
What happens: The template moves hi down by 1 so that hi is the last candidate. Without the shift, hi is one past the last candidate. The round-up midpoint can then be equal to hi, and the check is called with a position that is not a candidate. For a = [5, 6, 7] and a check that is always True, the loop calls the check with index 3, and a[3] raises an IndexError.
Example: a = [5, 6, 7], and every value passes the check a[i] < 10
Mistake: raises IndexErrorFix: returns 2
Gotcha 4: Using Lower Bound's check nums[i] >= target
Mistake
```
is_feasible = lambda i: nums[i] >= target
```
Fix
```
is_feasible = lambda i: nums[i] <= target
```
What happens: Upper Bound needs a check that reads True…True False…False. nums[i] >= target reads False…False True…True, which is the row for Lower Bound. The search then follows the wrong side. For nums = [1, 3, 5, 6] and target = 3, the check is True from index 1 on, so every probe passes, the search keeps moving right, and it returns 3. The last index with nums[i] <= 3 is 1.
Example: nums = [1, 3, 5, 6], target = 3
Mistake: returns 3Fix: returns 1
Gotcha 5: Using the answer as an index without checking it
Mistake
```
value = a[answer]
```
Fix
```
value = a[answer] if answer >= 0 else None
```
What happens: When no candidate is True, the answer is -1. In Python, a[-1] does not raise an error. It reads the last value of the list, and the code continues with a wrong value. Check answer >= 0 before you read a[answer].
Example: a = [5, 6, 7], x = 3: no value is at most 3
Mistake: returns 7Fix: returns None
Gotcha 6: Using the last True index as a count
Mistake
```
count = last_index
```
Fix
```
count = last_index + 1
```
What happens: Indices start at 0. So the number of values up to the last True index is that index plus 1. For a = [1, 2, 2, 3] and x = 2, the last index with a[i] <= 2 is 2, and the count is 3.
Example: a = [1, 2, 2, 3], x = 2
Mistake: returns 2Fix: returns 3
Gotcha 7: Expecting bisect_right to find the last True
Mistake
```
last = bisect.bisect_right(a, x)
```
Fix
```
last = bisect.bisect_right(a, x) - 1
```
What happens: bisect_right finds the first index where a[i] > x. That is a first True, not a last True. For a = [1, 2, 2, 3] and x = 2, it returns 3. The last index with a[i] <= 2 is 2, so subtract 1.
Example: a = [1, 2, 2, 3], x = 2
Mistake: returns 3Fix: returns 2

Not this one if…

You need the first value where a check turns True, the smallest letter greater than target, as in Find Smallest Letter Greater Than Target (LC 744). See Lower Bound
You only need to know whether some integer squares to exactly num, as in Valid Perfect Square (LC 367): a three-way compare can stop the moment mid * mid == num, with no boundary to find. See Exact Match
There is no formula or index to test: checking one guess means placing every ball greedily across the whole input, as in Magnetic Force Between Two Balls (LC 1552), so building that check is the real work. See Feasible Function

Theory

The question we build

What we know

A candidate is a possible answer, here a whole number k. The square k * k only gets larger when k gets larger, so the check k * k <= x is True for small k and False from some k on.

What the problem gives us

The input is x. The candidates are the whole numbers 0 to x, and the answer is the last candidate that passes the check fits.

The question we build

For x = 8, the checks for k = 0 to 8 read True, True, True, False, False, False, False, False, False. The last True is k = 2.

fits(k)

The last True is k = 2, because 2 * 2 = 4 is at most 8 and 3 * 3 = 9 is not.

Narrowing down to the template

The candidates are 0 to x, so the call is binary_search_upper_bound(0, x + 1, fits). Here hi = x + 1 is one past the last candidate, as in Lower Bound.

Step 1: Linear scan

Start at lo - 1, the position just before the first candidate. Move forward while the next candidate passes. The position where the scan stops is the last True.

Step 1: Linear scanPython

1		def last_true_scan(lo, hi, is_feasible):
2		last = lo - 1
3		while last + 1 < hi and is_feasible(last + 1):
4		last += 1
5		return last

Cost: O(N) checks for N candidates.

Step 2: Keep the last True

The scan checks the candidates in order. The halving loop checks only mid, and each check removes one side of the range. The table shows which parts mirror Lower Bound.

Step 2: Keep the last TruePython

1		def binary_search_upper_bound(lo: int, hi: int, is_feasible: Callable[[int], bool]) -> int:
2		"""Last candidate in [lo, hi) where is_feasible is True; lo - 1 when none is True."""
3		# lo becomes a known True, or the sentinel one before the first candidate; hi becomes the last candidate.
4		lo, hi = lo - 1, hi - 1
5
6		while lo < hi:
7		# 1. Compute the Ceiling Midpoint:
8		# Round mid up so lo < mid <= hi; rounding down would leave mid stuck at lo when one candidate remains.
9		mid = lo + (hi - lo + 1) // 2
10
11		# 2. Check the Midpoint:
12		# is_feasible(mid) shows which side of the flip mid is on: True at mid or before it, or False after it.
13		if is_feasible(mid):
14		# 3. Keep the Candidate:
15		# mid may be the last True, so keep it in the range by moving lo up to mid.
16		lo = mid
17		else:
18		# 4. Discard the Candidate:
19		# mid is False, so the last True must be strictly to the left of mid.
20		hi = mid - 1
21
22		# 5. Return the Boundary:
23		# The loop stops when lo equals hi; that position is the last True, or the sentinel when none was True.
24		return lo

Cost: O(T * log(N + 1)) time and O(1) space, where T is the cost of one check.

Item	Lower Bound	Upper Bound
Row	`False then True`	`True then False`
Internal bounds	`[lo, hi)`	`[lo - 1, hi - 1]`, including the sentinel
Midpoint	Floor	Ceiling: `lo < mid <= hi`
Passing check	`hi = mid`	`lo = mid`
Failing check	`lo = mid + 1`	`hi = mid - 1`

The shorter version

1. A range of candidates, range(lo, hi)

2. A sorted list, nums

2. A sorted list, numsPython

1		from bisect import bisect_right
2
3		# nums is sorted; insertion position after values <= target, minus 1.
4		last = bisect_right(nums, target, lo, hi) - 1
5		value = nums[last] if last >= lo else None
6
7		# Records are sorted by their numeric first field.
8		records = [(1, 'Ada'), (2, 'Bo'), (2, 'Cy'), (4, 'Di')]
9		last_record = bisect_right(records, 2, 1, 4, key=lambda record: record[0]) - 1 # 2

How to build is_feasible

Ask the same four questions as for Lower Bound, in this order:

Does this value still fit? Name it in words, for example fits.
Is the row True…True False…False? Draw the row on a tiny input. If the row has another shape, the check is wrong.
Can I evaluate the check for one proposed candidate using the input? State the work one evaluation performs. It may read neighbours, count values, or simulate a process.
What range [lo, hi) holds every possible answer? hi is one past the last candidate.

Here are two worked checks, each drawn on a tiny input.

k * (k + 1) // 2 <= n

Arranging Coins (LC 441) with n = 5. A staircase with k full rows needs k * (k + 1) // 2 coins. The candidates are 0 to n, so hi = n + 1 = 6.

a[i]

a[i] <= x

The last index with a[i] <= 2 in [1, 2, 2, 3] is 2.

Choosing lo and hi

You look for	Candidates	Call	Nothing is True
The last index with `a[i] <= x`	indices `0 … len - 1`	`binary_search_upper_bound(0, len(a), check)`	`-1`, which means no such index
The largest `k` with `k * k <= x`	values `0 … x`	`binary_search_upper_bound(0, x + 1, check)`	`-1` (this never happens for Sqrt(x), because `k = 0` always fits)

The contract

Item	Upper Bound
Range	Half-open `[lo, hi)`, the same as Lower Bound.
The check	Takes one candidate. Returns `True` or `False`. Must be True…True False…False over `[lo, hi)`.
Returns	The last True.
No candidate is True	`lo - 1` of the original call.
Every candidate is True	`hi - 1` of the original call, which is the last candidate.
Cost	`O(T * log N)` time and `O(1)` space. `N = hi - lo`, and `T` is the cost of one check.

For Sqrt(x) (LC 69), mySqrt(0) is 0 and mySqrt(1) is 1, because k = 0 always fits.

Insertion positions: last True and counts

Take a = [1, 2, 2, 2, 4] and x = 2. The equal values occupy the indices 1 to 3.

Question	Our helper	Python
First index with `a[i] >= x`	`binary_search_lower_bound(0, len(a), lambda i: a[i] >= x)` gives 1	`bisect_left(a, x)` gives 1
Last index with `a[i] <= x`	`binary_search_upper_bound(0, len(a), lambda i: a[i] <= x)` gives 3	`bisect_right(a, x) - 1` gives 3
Position after all values `<= x`	Upper Bound result + 1 gives 4	`bisect_right(a, x)` gives 4

bisect_left puts the position before the equal values. bisect_right puts it after them. Our Upper Bound returns the last passing candidate, which is one position before bisect_right.

For a window, pass lo and hi. The returned position is an index in the whole list, not an offset in the window.

Code / Blueprint

left = bisect_left(nums, target, lo, hi)
right = bisect_right(nums, target, lo, hi)

Values in nums[lo:hi]	Count
< target	left - lo
<= target	right - lo
== target	right - left
> target	hi - right
>= target	hi - left

Overflow in the square-root check

The check for mySqrt is k * k <= x. The check multiplies k by itself, so it can overflow in a language with fixed-width integers.

Real-world use

Say it in an interview

About 60 seconds, for Sqrt(x) (LC 69):

"I use Upper Bound to find the largest k whose square is at most x, because the check reads True, then False. I pass [0, x + 1), and the template shifts both bounds down by 1. The midpoint rounds up, so lo < mid <= hi. A passing mid becomes lo, and a failing mid makes hi = mid - 1. The loop returns lo when lo == hi, in O(log(x + 1)) time and O(1) space. The trap is the rounded-down midpoint, which leaves lo = mid stuck when hi == lo + 1."

Common Questions

How do you get the last True with Lower Bound instead?: Ask for the first index where the opposite check is True, then subtract 1. For Sqrt(x) (LC 69), binary_search_lower_bound(0, x + 1, lambda k: k * k > x) - 1 gives the same answer as Upper Bound, including x = 0 and x = 1. Upper Bound avoids the opposite check and the subtraction.
How do the two cards solve Find First and Last Position of Element in Sorted Array (LC 34)?: The first position is Lower Bound with nums[i] >= target. The last position is Upper Bound with nums[i] <= target. The target is present only when the first position is not after the last position. Otherwise the answer is [-1, -1]. For nums = [1, 2, 2, 2, 4] and target = 2, the positions are 1 and 3.

Practice

Canonical LeetCode:Sqrt(x) (LC 69)Arranging Coins (LC 441)Find First and Last Position of Element in Sorted Array (LC 34)Time Based Key-Value Store (LC 981)