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 and Kth Smallest, which you haven’t finished yet.

P3HardBuilt on Lower Bound~6 min speedrun

Partition Binary Search (Median of Two Sorted Arrays)

Built on

Kth SmallestThe candidate is how many values to take from the shorter list, not a value, and the check compares the values on both sides of the cut.

Median of Two Sorted Arrays (LC 4)(opens leetcode.com)

You're given two already-sorted arrays, nums1 (size m) and nums2 (size n). Without necessarily merging them, work out the median value of all m + n numbers combined.

Target an overall running time of O(log(m + n)).

Example 1

Input:nums1 = [1,3], nums2 = [2]

Output:2.00000

merged array = [1,2,3] and median is 2.

Median of Two Sorted Arrays

two sorted lists ➔ search how many values to take from the shorter list ➔ the first cut where right1 is at least left2

Spot it when: The statement asks for the median, or the k-th smallest value, of two lists that are already sorted, and the limit asks for O(log(M + N)) or better, so merging is too slow.

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: Every candidate below lo is False, and the first True is never after hi, because the last candidate, min(m, k), is always True.

A cut takes i values from the shorter list nums1 and k - i values from nums2, so the left side holds exactly k values. left1 and right1 are the values just left and right of the cut in nums1, and left2 and right2 are the same in nums2. When left1 <= right2 and left2 <= right1, the largest left value, max(left1, left2), is the k-th smallest. Each list is sorted, so only these two pairs cross the cut. As i grows, right1 can only grow and left2 can only shrink, so right1_at_least_left2(i) is False and then True, and Lower Bound returns its first True. At the first True, left2 <= right1 holds because the check is True. left1 < right2 holds because the check one step before was False. When the first True is lo, there is no step before, and the same fact holds because left1 is float('-inf') when lo is 0, or right2 is float('inf') when lo is k - n. The trap: when i == m there is no nums1[i], and when k - i == 0 there is no nums2[k - i - 1], so write float('inf') and float('-inf') for those values, because reading the list raises IndexError.

See it run

Median of Two Arrays: Lower Bound over the cut, step by step

k 7lo 0hi 7mid none

The top row lists the cut i, the number of values taken from nums1. The shorter list is called nums1. A cell with inf stands for a missing value.

lo the fewest values nums1 can give so far
hi one past the most values nums1 can give
mid the position the check reads now
left1 the last value nums1 gives to the left side
right1 the first value nums1 keeps for the right side
left2 the last value nums2 gives to the left side
right2 the first value nums2 keeps for the right side
lo+mid lo and mid are at the same position
answer the cut where the loop ends

Find the 7-th smallest value. The cut i can take 0 up to 6 values from nums1, so lo = 0 and hi = 7.

cut i

0lo

endhi

nums1

inf

nums2

inf

1 / 11

Gotchas1 of 5

The trap
Gotcha 1: Reading past the end of a list without float('inf')
Mistake
```
right1 = nums1[i]
```
Fix
```
right1 = nums1[i] if i < m else float('inf')
```
What happens: When i == m, the cut is after the last value of nums1, so there is no nums1[i]. Python raises IndexError. The missing value must count as larger than every value, so write float('inf') for it. The same holds for left2 when k - i == 0, where float('-inf') is the missing value.
Example: nums1 = [1, 3], nums2 = [2, 4], k = 4
Mistake: raises IndexErrorFix: returns 4
Gotcha 2: Starting lo at 0 instead of max(0, k - n)
Mistake
```
lo = 0
```
Fix
```
lo = max(0, k - n)
```
What happens: When k is larger than n, at least k - n values must come from nums1. With lo = 0, the search tries i = 0, where j = k is larger than n. Then nums2[k - i - 1] is past the end of nums2, and Python raises IndexError.
Example: nums1 = [3], nums2 = [1, 2], k = 3
Mistake: raises IndexErrorFix: returns 3
Gotcha 3: Reading nums2[k - i] instead of nums2[k - i - 1]
Mistake
```
right1 = nums1[i] if i < m else float('inf')
left2 = nums2[k - i] if k - i > 0 else float('-inf')
```
Fix
```
right1 = nums1[i] if i < m else float('inf')
left2 = nums2[k - i - 1] if k - i > 0 else float('-inf')
```
What happens: The cut takes the first k - i values of nums2, so the last value on the left side has index k - i - 1. The index k - i is the first value on the right side, which is right2. The check then compares right1 with the wrong value. For [1, 3], [2, 4] and k = 2, the search returns 3 instead of 2. For k = 3, the index can also go past the end of nums2, and Python raises IndexError.
Example: nums1 = [1, 3], nums2 = [2, 4], k = 2
Mistake: returns 3Fix: returns 2
Gotcha 4: Making one call when the total is even
Mistake
```
return float(kth_smallest_of_two(nums1, nums2, k))
```
Fix
```
lower_middle = kth_smallest_of_two(nums1, nums2, k)
```
What happens: When the total is even, the median is the mean of two values, the k-th and the next one. One call returns only the k-th. For [1, 2] and [3, 4], one call returns 2.0, and the median is 2.5.
Example: nums1 = [1, 2], nums2 = [3, 4]
Mistake: returns 2.0Fix: returns 2.5
Gotcha 5: Averaging with // instead of /
Mistake
```
return (lower_middle + upper_middle) // 2
```
Fix
```
return (lower_middle + upper_middle) / 2
```
What happens: // rounds down to a whole number. The median of [1, 2] and [3, 4] is 2.5, but (2 + 3) // 2 is 2. Use / 2.
Example: nums1 = [1, 2], nums2 = [3, 4]
Mistake: returns 2Fix: returns 2.5

Not this one if…

There are many sorted rows, not two, as in Median of a Row Wise Sorted Matrix (LC 2387), so one cut no longer decides where all the other cuts go. See Kth Smallest

Theory

The question we build

What we know

Both lists are sorted. The median is a rank in the sorted order of all values together, so the work is to find the k-th smallest value. We do not search for a value. We search for the number of values to take from one list.

What the problem gives us

The problem gives two lists and asks for a median, but not for k. The note From k to the median, below, shows how k comes from the total length. First we find the k-th smallest value for any k.

The question we build

For each i we ask: "is nums1[i] at least the last value taken from nums2?" We use nums1 = [1, 3, 8], nums2 = [2, 4, 6, 7] and k = 4. The candidates are i = 0, 1, 2, 3: the number of values taken from nums1. The answers are False, False, True, True. The first True is i = 2: two values from nums1 (1 and 3) and two from nums2 (2 and 4). The largest left value is 4.

right1_at_least_left2(i)

At i = 1 the check compares right1 = 3 with left2 = 6. At i = 2 it compares right1 = 8 with left2 = 4.

Narrowing down to the template

The first True is the right cut, so the template applies. The note Choosing lo and hi, below, gives the range and the call.

Step 1: Merge and read the middle

The k-th smallest is the value at index k - 1 of the two lists sorted together. The merge states this in a few lines. It reads every value.

Step 1: Merge and read the middlePython

1		def kth_smallest_merged(nums1, nums2, k):
2		merged = nums1 + nums2
3		merged.sort()
4		return merged[k - 1]

Cost: O((M + N) log(M + N)).

Step 2: The cut loop, written out

Take i values from nums1 and j = k - i values from nums2. The loop has three cases: the cut is too far right (left1 > right2), too far left (left2 > right1), or balanced. In the balanced case, the largest left value is the k-th smallest.

Step 2: The cut loop, written outPython

1		def kth_smallest_written_out(nums1, nums2, k):
2		if k < 1 or k > len(nums1) + len(nums2):
3		raise ValueError("k is out of range")
4		if len(nums1) > len(nums2):
5		nums1, nums2 = nums2, nums1 # search the shorter list
6		m, n = len(nums1), len(nums2)
7		lo = max(0, k - n) # fewest values we can take from nums1
8		hi = min(m, k) + 1 # one past the most values we can take from nums1
9		answer = None
10
11		while lo < hi:
12		i = lo + (hi - lo) // 2 # cut in nums1
13		j = k - i # matching cut in nums2
14		left1 = nums1[i - 1] if i > 0 else float('-inf')
15		right1 = nums1[i] if i < m else float('inf')
16		left2 = nums2[j - 1] if j > 0 else float('-inf')
17		right2 = nums2[j] if j < n else float('inf')
18
19		if left1 > right2: # too many from nums1: the cut is too far right
20		hi = i
21		elif left2 > right1: # too few from nums1: the cut is too far left
22		lo = i + 1
23		else: # balanced: the left side holds the k smallest values
24		answer = max(left1, left2)
25		hi = i # keep looking; every balanced cut gives the same answer
26
27		return answer

Cost: O(log min(M, N)). The loop halves the range of cuts every pass.

Step 3: Ask one question

The loop asks the same thing from two sides. The cases left1 > right2 and balanced both set hi = i. The case left2 > right1 sets lo = i + 1. So one question, right1_at_least_left2(i), replaces the three cases: True sets hi = i, and False sets lo = i + 1. The answer max(left1, left2) is read once, after the search.

Step 3: Ask one questionPython

1	+	New line: def kth_smallest_of_two(nums1: List[int], nums2: List[int], k: int) -> int:
2		if k < 1 or k > len(nums1) + len(nums2):
3		raise ValueError("k is out of range")
4		if len(nums1) > len(nums2):
5		nums1, nums2 = nums2, nums1 # search the shorter list
6		m, n = len(nums1), len(nums2)
7
8	+	New line: def right1_at_least_left2(i: int) -> bool: # take i values from nums1 and k - i from nums2
9	+	New line: right1 = nums1[i] if i < m else float('inf')
10	+	New line: left2 = nums2[k - i - 1] if k - i > 0 else float('-inf')
11	+	New line: return right1 >= left2
12
13		lo = max(0, k - n) # fewest values we can take from nums1
14		hi = min(m, k) + 1 # one past the most values we can take from nums1
15	+	New line: i = binary_search_lower_bound(lo, hi, right1_at_least_left2)
16	+	New line: left1 = nums1[i - 1] if i > 0 else float('-inf')
17	+	New line: left2 = nums2[k - i - 1] if k - i > 0 else float('-inf')
18	+	New line: return max(left1, left2) # the largest value on the left side is the k-th smallest

Cost: O(log min(M, N)).

Choosing lo and hi

You look for	Candidates	Call	Nothing is True
The k-th smallest of two sorted lists	`i = max(0, k - n)` … `min(m, k)`, the values taken from the shorter list	`binary_search_lower_bound(max(0, k - n), min(m, k) + 1, right1_at_least_left2)`	This never happens: the last candidate always passes.

The candidates are counts of values, not values. lo is not 0 when k is larger than n. Then at least k - n values must come from nums1. hi - 1 is the last candidate. At that cut, nums1[i] does not exist, or no value is taken from nums2, so the check is True. In the example, k = 1 gives the range [0, 2) and the result 1, the smallest value. k = 7 gives lo = 3 and hi = 4, so there is one candidate, and the result is 8, the largest value.

From k to the median

The median is the k-th smallest for k = (total + 1) // 2. For an odd total, one call is enough. For an even total, the median is the mean of the k-th and the next value. It needs two calls, with k and k + 1. For [1, 2] and [3, 4], the 2nd smallest is 2 and the 3rd smallest is 3, so the median is 2.5. Divide with / 2. The division // 2 gives 2 here.

The cost without merging

nums1, the shorter list, has m + 1 possible cuts, so the search runs at most floor(log2(m + 1)) + 1 passes. That is 10 passes at LeetCode's limit of m = 1000, however long nums2 is. The search never builds a merged copy. The state is only the range [lo, hi) of cuts and four boundary values (left1, right1, left2, right2). Each pass reads two values, so the whole search reads O(log(min(M, N))) values. This is useful when the two lists are too large to copy, or are stored on a slow disk or a remote server.

Real-world use

Two sorted shards, such as two sorted files or two sorted partitions of a table, give the median (or any percentile) of their union without being merged. The cut search reads only the values next to each cut.

Say it in an interview

About 60 seconds, for Median of Two Sorted Arrays (LC 4):

"This is Lower Bound over a count of values. A cut takes i values from the shorter list and k - i from the other, so the left side holds exactly k values. The check right1 >= left2 is False and then True, so Lower Bound finds the first valid cut. The largest left value is the k-th smallest, and an even total needs a second call for k + 1. A missing value at an edge is float('inf') or float('-inf'). The time is O(log min(M, N)) and the space is O(1)."

Common Questions

Why search the shorter list?: It only lowers the cost. The shorter list has fewer candidates, so the time is O(log min(M, N)) instead of O(log max(M, N)). The range [max(0, k - n), min(m, k) + 1) keeps every read inside both lists for either order, so the answer stays correct if you search the longer list.
What if one list is empty?: The shorter list is the empty one, so m is 0 and the range [0, 1) has one candidate. The result is the k-th value of the other list. For [] and [1, 2], findMedianSortedArrays returns 1.5.
Do equal values break the cut?: No. A tie between right1 and left2 makes the check True, and the cut is valid. The largest left value is the same for every valid cut, so the answer does not depend on which equal value sits on which side.
How would you find a percentile of two large sorted files?: Use the same helper with k = ceil(p / 100 * total), the nearest-rank percentile. The search reads only O(log min(M, N)) values, so neither file is loaded or merged.

Practice

Canonical LeetCode:Median of Two Sorted Arrays (LC 4)

The older version of this card searched the cut with a closed loop, while lo <= hi, and checked both sides of the cut in one if. It also found the median inside the loop, with half = (m + n + 1) // 2. This course uses the template with the range [lo, hi), one check that asks a single question, and the k-th smallest helper.

The classic loop

Old Way

Python

1	from typing import List
2
3	def find_median_sorted_arrays(nums1: List[int], nums2: List[int]) -> float:
4	"""Median of Two Sorted Arrays: binary search on the cut in the shorter array.
5	Time: O(log(min(M, N))) \| Space: O(1)
6	"""
7	if len(nums1) > len(nums2):
8	nums1, nums2 = nums2, nums1 # Search strictly across shorter sequence
9
10	m, n = len(nums1), len(nums2)
11	half = (m + n + 1) // 2 # Size of the combined left half
12	lo, hi = 0, m
13
14	while lo <= hi:
15	i = lo + (hi - lo) // 2 # Cut in nums1
16	j = half - i # Matching cut in nums2
17
18	left1 = nums1[i - 1] if i > 0 else float('-inf')
19	right1 = nums1[i] if i < m else float('inf')
20	left2 = nums2[j - 1] if j > 0 else float('-inf')
21	right2 = nums2[j] if j < n else float('inf')
22
23	if left1 <= right2 and left2 <= right1: # Equilibrium verified
24	if (m + n) % 2 == 1:
25	return float(max(left1, left2))
26	return (max(left1, left2) + min(right1, right2)) / 2.0
27	elif left1 > right2:
28	hi = i - 1 # Cut i too far right
29	else:
30	lo = i + 1 # Cut i too far left
31
32	return 0.0

From the classic loop to our template

Old Way line	In our template	Why
half = (m + n + 1) // 2	k = (total + 1) // 2	The same size of the left half. The new code names it `k` and passes it to the helper.
lo, hi = 0, m	lo = max(0, k - n) and hi = min(m, k) + 1	The older range allows cuts that read past the end of `nums2`. The new range keeps every cut inside both lists.
while lo <= hi: with three branches	binary_search_lower_bound(lo, hi, right1_at_least_left2)	The same search, written once as the template, with one question instead of three branches.
if (m + n) % 2 == 1: ... else: ... / 2.0	one call for an odd total, two calls for an even total	The helper returns the k-th smallest only, so the even total calls it with `k` and `k + 1`.

When the classic form is fine

Use it when an interviewer asks for this form, or when the code base already uses it. It is the same search. The template only gives the loop a name and splits the median from the cut.

Gotchas of the classic loop

Gotchas1 of 3

The trap
Gotcha 1: Searching the longer array instead of the shorter one
Mistake
```
if len(nums1) < len(nums2):
```
Fix
```
if len(nums1) > len(nums2):
```
What happens: The cut j = half - i must stay between 0 and n, the length of nums2. When nums1 is the shorter array, every i from 0 to m keeps j in that range. When nums1 is the longer array, j can go below 0 or above n. Then nums2[j - 1] reads a wrong value or raises an IndexError. Searching the shorter array also makes the cost O(log(min(m, n))).
Example: nums1 = [1, 4, 9], nums2 = []
Mistake: raises IndexErrorFix: returns 4.0
Gotcha 2: Reading nums1[i - 1] when i == 0
Mistake
```
left1 = nums1[i - 1]
```
Fix
```
left1 = nums1[i - 1] if i > 0 else float('-inf')
```
What happens: When i == 0, the left part of nums1 is empty. nums1[i - 1] is then nums1[-1], and Python reads the last value of nums1 without an error. In the example, i = 0 sets left1 = nums1[-1] = 3. The cut check passes, and the median comes out as max(3, 2) = 3 instead of 2. -inf stands for an empty left part, and +inf for an empty right part.
Example: nums1 = [3], nums2 = [1, 2]
Mistake: returns 3.0Fix: returns 2.0
Gotcha 3: Writing half = (m + n) // 2
Mistake
```
half = (m + n) // 2
```
Fix
```
half = (m + n + 1) // 2
```
What happens: When m + n is odd, one half gets the extra value. (m + n + 1) // 2 puts it in the left half. So the median is max(left1, left2), which is what the code returns. (m + n) // 2 puts the extra value in the right half. The code still returns max(left1, left2), which is then the value just below the median.
Example: nums1 = [1, 3], nums2 = [2]
Mistake: returns 1.0Fix: returns 2.0

Earlier signals

Two sorted arrays must be combined (median, k-th element) without merging them.

Earlier invariant

i + j == half at every step, and the correct cut i always lies in [lo, hi].

Earlier direction

dual sequences ➔ cross-boundary bisection ➔ equilibrium cut

Earlier description

The median splits both arrays together into two equal halves, so choosing the cut i in the shorter array forces the cut j = half - i in the other. The cut is right exactly when left1 <= right2 and left2 <= right1; if left1 > right2, i is too far right, otherwise too far left, so i can be binary-searched, with -inf/+inf standing in for a cut at an array's edge. The trap is searching the longer array: then j = half - i can leave [0, n]. Without the swap, nums1 = [1, 4, 9], nums2 = [] tries i = 1, so j = 1, and reading nums2[j - 1] crashes.

Earlier template

Python

1	from typing import List
2
3	def find_median_sorted_arrays(nums1: List[int], nums2: List[int]) -> float:
4	"""Median of Two Sorted Arrays: binary search on the cut in the shorter array.
5	Time: O(log(min(M, N))) \| Space: O(1)
6	"""
7	if len(nums1) > len(nums2):
8	nums1, nums2 = nums2, nums1 # Search strictly across shorter sequence
9
10	m, n = len(nums1), len(nums2)
11	half = (m + n + 1) // 2 # Size of the combined left half
12	lo, hi = 0, m
13
14	while lo <= hi:
15	i = lo + (hi - lo) // 2 # Cut in nums1
16	j = half - i # Matching cut in nums2
17
18	left1 = nums1[i - 1] if i > 0 else float('-inf')
19	right1 = nums1[i] if i < m else float('inf')
20	left2 = nums2[j - 1] if j > 0 else float('-inf')
21	right2 = nums2[j] if j < n else float('inf')
22
23	if left1 <= right2 and left2 <= right1: # Equilibrium verified
24	if (m + n) % 2 == 1:
25	return float(max(left1, left2))
26	return (max(left1, left2) + min(right1, right2)) / 2.0
27	elif left1 > right2:
28	hi = i - 1 # Cut i too far right
29	else:
30	lo = i + 1 # Cut i too far left
31
32	return 0.0

Earlier gotchas

Searching the longer array instead of the shorter one

The cut j = half - i must stay between 0 and n, the length of nums2. When nums1 is the shorter array, every i from 0 to m keeps j in that range. When nums1 is the longer array, j can go below 0 or above n. Then nums2[j - 1] reads a wrong value or raises an IndexError. Searching the shorter array also makes the cost O(log(min(m, n))).

Reading nums1[i - 1] when i == 0

When i == 0, the left part of nums1 is empty. nums1[i - 1] is then nums1[-1], and Python reads the last value of nums1 without an error. In the example, i = 0 sets left1 = nums1[-1] = 3. The cut check passes, and the median comes out as max(3, 2) = 3 instead of 2. -inf stands for an empty left part, and +inf for an empty right part.

Writing half = (m + n) // 2

When m + n is odd, one half gets the extra value. (m + n + 1) // 2 puts it in the left half. So the median is max(left1, left2), which is what the code returns. (m + n) // 2 puts the extra value in the right half. The code still returns max(left1, left2), which is then the value just below the median.

Theory Context•Binary Search Boundary

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

P3HardBuilt on Lower Bound~6 min speedrun

Partition Binary Search (Median of Two Sorted Arrays)

Built on

Kth SmallestThe candidate is how many values to take from the shorter list, not a value, and the check compares the values on both sides of the cut.

Median of Two Sorted Arrays (LC 4)(opens leetcode.com)

You're given two already-sorted arrays, nums1 (size m) and nums2 (size n). Without necessarily merging them, work out the median value of all m + n numbers combined.

Target an overall running time of O(log(m + n)).

Example 1

Input:nums1 = [1,3], nums2 = [2]

Output:2.00000

merged array = [1,2,3] and median is 2.

Median of Two Sorted Arrays

two sorted lists ➔ search how many values to take from the shorter list ➔ the first cut where right1 is at least left2

Spot it when: The statement asks for the median, or the k-th smallest value, of two lists that are already sorted, and the limit asks for O(log(M + N)) or better, so merging is too slow.

Median of Two Sorted Arrays

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: Every candidate below lo is False, and the first True is never after hi, because the last candidate, min(m, k), is always True.

See it run

Median of Two Arrays: Lower Bound over the cut, step by step

k 7lo 0hi 7mid none

The top row lists the cut i, the number of values taken from nums1. The shorter list is called nums1. A cell with inf stands for a missing value.

lo the fewest values nums1 can give so far
hi one past the most values nums1 can give
mid the position the check reads now
left1 the last value nums1 gives to the left side
right1 the first value nums1 keeps for the right side
left2 the last value nums2 gives to the left side
right2 the first value nums2 keeps for the right side
lo+mid lo and mid are at the same position
answer the cut where the loop ends

Find the 7-th smallest value. The cut i can take 0 up to 6 values from nums1, so lo = 0 and hi = 7.

cut i

0lo

endhi

nums1

inf

nums2

inf

1 / 11

Gotchas1 of 5

The trap
Gotcha 1: Reading past the end of a list without float('inf')
Mistake
```
right1 = nums1[i]
```
Fix
```
right1 = nums1[i] if i < m else float('inf')
```
What happens: When i == m, the cut is after the last value of nums1, so there is no nums1[i]. Python raises IndexError. The missing value must count as larger than every value, so write float('inf') for it. The same holds for left2 when k - i == 0, where float('-inf') is the missing value.
Example: nums1 = [1, 3], nums2 = [2, 4], k = 4
Mistake: raises IndexErrorFix: returns 4
Gotcha 2: Starting lo at 0 instead of max(0, k - n)
Mistake
```
lo = 0
```
Fix
```
lo = max(0, k - n)
```
What happens: When k is larger than n, at least k - n values must come from nums1. With lo = 0, the search tries i = 0, where j = k is larger than n. Then nums2[k - i - 1] is past the end of nums2, and Python raises IndexError.
Example: nums1 = [3], nums2 = [1, 2], k = 3
Mistake: raises IndexErrorFix: returns 3
Gotcha 3: Reading nums2[k - i] instead of nums2[k - i - 1]
Mistake
```
right1 = nums1[i] if i < m else float('inf')
left2 = nums2[k - i] if k - i > 0 else float('-inf')
```
Fix
```
right1 = nums1[i] if i < m else float('inf')
left2 = nums2[k - i - 1] if k - i > 0 else float('-inf')
```
What happens: The cut takes the first k - i values of nums2, so the last value on the left side has index k - i - 1. The index k - i is the first value on the right side, which is right2. The check then compares right1 with the wrong value. For [1, 3], [2, 4] and k = 2, the search returns 3 instead of 2. For k = 3, the index can also go past the end of nums2, and Python raises IndexError.
Example: nums1 = [1, 3], nums2 = [2, 4], k = 2
Mistake: returns 3Fix: returns 2
Gotcha 4: Making one call when the total is even
Mistake
```
return float(kth_smallest_of_two(nums1, nums2, k))
```
Fix
```
lower_middle = kth_smallest_of_two(nums1, nums2, k)
```
What happens: When the total is even, the median is the mean of two values, the k-th and the next one. One call returns only the k-th. For [1, 2] and [3, 4], one call returns 2.0, and the median is 2.5.
Example: nums1 = [1, 2], nums2 = [3, 4]
Mistake: returns 2.0Fix: returns 2.5
Gotcha 5: Averaging with // instead of /
Mistake
```
return (lower_middle + upper_middle) // 2
```
Fix
```
return (lower_middle + upper_middle) / 2
```
What happens: // rounds down to a whole number. The median of [1, 2] and [3, 4] is 2.5, but (2 + 3) // 2 is 2. Use / 2.
Example: nums1 = [1, 2], nums2 = [3, 4]
Mistake: returns 2Fix: returns 2.5

Not this one if…

There are many sorted rows, not two, as in Median of a Row Wise Sorted Matrix (LC 2387), so one cut no longer decides where all the other cuts go. See Kth Smallest

Theory

The question we build

What we know

What the problem gives us

The problem gives two lists and asks for a median, but not for k. The note From k to the median, below, shows how k comes from the total length. First we find the k-th smallest value for any k.

The question we build

right1_at_least_left2(i)

At i = 1 the check compares right1 = 3 with left2 = 6. At i = 2 it compares right1 = 8 with left2 = 4.

Narrowing down to the template

The first True is the right cut, so the template applies. The note Choosing lo and hi, below, gives the range and the call.

Step 1: Merge and read the middle

The k-th smallest is the value at index k - 1 of the two lists sorted together. The merge states this in a few lines. It reads every value.

Step 1: Merge and read the middlePython

1		def kth_smallest_merged(nums1, nums2, k):
2		merged = nums1 + nums2
3		merged.sort()
4		return merged[k - 1]

Cost: O((M + N) log(M + N)).

Step 2: The cut loop, written out

Step 2: The cut loop, written outPython

1		def kth_smallest_written_out(nums1, nums2, k):
2		if k < 1 or k > len(nums1) + len(nums2):
3		raise ValueError("k is out of range")
4		if len(nums1) > len(nums2):
5		nums1, nums2 = nums2, nums1 # search the shorter list
6		m, n = len(nums1), len(nums2)
7		lo = max(0, k - n) # fewest values we can take from nums1
8		hi = min(m, k) + 1 # one past the most values we can take from nums1
9		answer = None
10
11		while lo < hi:
12		i = lo + (hi - lo) // 2 # cut in nums1
13		j = k - i # matching cut in nums2
14		left1 = nums1[i - 1] if i > 0 else float('-inf')
15		right1 = nums1[i] if i < m else float('inf')
16		left2 = nums2[j - 1] if j > 0 else float('-inf')
17		right2 = nums2[j] if j < n else float('inf')
18
19		if left1 > right2: # too many from nums1: the cut is too far right
20		hi = i
21		elif left2 > right1: # too few from nums1: the cut is too far left
22		lo = i + 1
23		else: # balanced: the left side holds the k smallest values
24		answer = max(left1, left2)
25		hi = i # keep looking; every balanced cut gives the same answer
26
27		return answer

Cost: O(log min(M, N)). The loop halves the range of cuts every pass.

Step 3: Ask one question

Step 3: Ask one questionPython

1	+	New line: def kth_smallest_of_two(nums1: List[int], nums2: List[int], k: int) -> int:
2		if k < 1 or k > len(nums1) + len(nums2):
3		raise ValueError("k is out of range")
4		if len(nums1) > len(nums2):
5		nums1, nums2 = nums2, nums1 # search the shorter list
6		m, n = len(nums1), len(nums2)
7
8	+	New line: def right1_at_least_left2(i: int) -> bool: # take i values from nums1 and k - i from nums2
9	+	New line: right1 = nums1[i] if i < m else float('inf')
10	+	New line: left2 = nums2[k - i - 1] if k - i > 0 else float('-inf')
11	+	New line: return right1 >= left2
12
13		lo = max(0, k - n) # fewest values we can take from nums1
14		hi = min(m, k) + 1 # one past the most values we can take from nums1
15	+	New line: i = binary_search_lower_bound(lo, hi, right1_at_least_left2)
16	+	New line: left1 = nums1[i - 1] if i > 0 else float('-inf')
17	+	New line: left2 = nums2[k - i - 1] if k - i > 0 else float('-inf')
18	+	New line: return max(left1, left2) # the largest value on the left side is the k-th smallest

Cost: O(log min(M, N)).

Choosing lo and hi

You look for	Candidates	Call	Nothing is True
The k-th smallest of two sorted lists	`i = max(0, k - n)` … `min(m, k)`, the values taken from the shorter list	`binary_search_lower_bound(max(0, k - n), min(m, k) + 1, right1_at_least_left2)`	This never happens: the last candidate always passes.

From k to the median

The cost without merging

Real-world use

Say it in an interview

About 60 seconds, for Median of Two Sorted Arrays (LC 4):

"This is Lower Bound over a count of values. A cut takes i values from the shorter list and k - i from the other, so the left side holds exactly k values. The check right1 >= left2 is False and then True, so Lower Bound finds the first valid cut. The largest left value is the k-th smallest, and an even total needs a second call for k + 1. A missing value at an edge is float('inf') or float('-inf'). The time is O(log min(M, N)) and the space is O(1)."

Common Questions

Why search the shorter list?: It only lowers the cost. The shorter list has fewer candidates, so the time is O(log min(M, N)) instead of O(log max(M, N)). The range [max(0, k - n), min(m, k) + 1) keeps every read inside both lists for either order, so the answer stays correct if you search the longer list.
What if one list is empty?: The shorter list is the empty one, so m is 0 and the range [0, 1) has one candidate. The result is the k-th value of the other list. For [] and [1, 2], findMedianSortedArrays returns 1.5.
Do equal values break the cut?: No. A tie between right1 and left2 makes the check True, and the cut is valid. The largest left value is the same for every valid cut, so the answer does not depend on which equal value sits on which side.
How would you find a percentile of two large sorted files?: Use the same helper with k = ceil(p / 100 * total), the nearest-rank percentile. The search reads only O(log min(M, N)) values, so neither file is loaded or merged.

Practice

Canonical LeetCode:Median of Two Sorted Arrays (LC 4)

The classic loop

Old Way

Python

1	from typing import List
2
3	def find_median_sorted_arrays(nums1: List[int], nums2: List[int]) -> float:
4	"""Median of Two Sorted Arrays: binary search on the cut in the shorter array.
5	Time: O(log(min(M, N))) \| Space: O(1)
6	"""
7	if len(nums1) > len(nums2):
8	nums1, nums2 = nums2, nums1 # Search strictly across shorter sequence
9
10	m, n = len(nums1), len(nums2)
11	half = (m + n + 1) // 2 # Size of the combined left half
12	lo, hi = 0, m
13
14	while lo <= hi:
15	i = lo + (hi - lo) // 2 # Cut in nums1
16	j = half - i # Matching cut in nums2
17
18	left1 = nums1[i - 1] if i > 0 else float('-inf')
19	right1 = nums1[i] if i < m else float('inf')
20	left2 = nums2[j - 1] if j > 0 else float('-inf')
21	right2 = nums2[j] if j < n else float('inf')
22
23	if left1 <= right2 and left2 <= right1: # Equilibrium verified
24	if (m + n) % 2 == 1:
25	return float(max(left1, left2))
26	return (max(left1, left2) + min(right1, right2)) / 2.0
27	elif left1 > right2:
28	hi = i - 1 # Cut i too far right
29	else:
30	lo = i + 1 # Cut i too far left
31
32	return 0.0

From the classic loop to our template

Old Way line	In our template	Why
half = (m + n + 1) // 2	k = (total + 1) // 2	The same size of the left half. The new code names it `k` and passes it to the helper.
lo, hi = 0, m	lo = max(0, k - n) and hi = min(m, k) + 1	The older range allows cuts that read past the end of `nums2`. The new range keeps every cut inside both lists.
while lo <= hi: with three branches	binary_search_lower_bound(lo, hi, right1_at_least_left2)	The same search, written once as the template, with one question instead of three branches.
if (m + n) % 2 == 1: ... else: ... / 2.0	one call for an odd total, two calls for an even total	The helper returns the k-th smallest only, so the even total calls it with `k` and `k + 1`.

When the classic form is fine

Use it when an interviewer asks for this form, or when the code base already uses it. It is the same search. The template only gives the loop a name and splits the median from the cut.

Gotchas of the classic loop

Gotchas1 of 3

The trap
Gotcha 1: Searching the longer array instead of the shorter one
Mistake
```
if len(nums1) < len(nums2):
```
Fix
```
if len(nums1) > len(nums2):
```
What happens: The cut j = half - i must stay between 0 and n, the length of nums2. When nums1 is the shorter array, every i from 0 to m keeps j in that range. When nums1 is the longer array, j can go below 0 or above n. Then nums2[j - 1] reads a wrong value or raises an IndexError. Searching the shorter array also makes the cost O(log(min(m, n))).
Example: nums1 = [1, 4, 9], nums2 = []
Mistake: raises IndexErrorFix: returns 4.0
Gotcha 2: Reading nums1[i - 1] when i == 0
Mistake
```
left1 = nums1[i - 1]
```
Fix
```
left1 = nums1[i - 1] if i > 0 else float('-inf')
```
What happens: When i == 0, the left part of nums1 is empty. nums1[i - 1] is then nums1[-1], and Python reads the last value of nums1 without an error. In the example, i = 0 sets left1 = nums1[-1] = 3. The cut check passes, and the median comes out as max(3, 2) = 3 instead of 2. -inf stands for an empty left part, and +inf for an empty right part.
Example: nums1 = [3], nums2 = [1, 2]
Mistake: returns 3.0Fix: returns 2.0
Gotcha 3: Writing half = (m + n) // 2
Mistake
```
half = (m + n) // 2
```
Fix
```
half = (m + n + 1) // 2
```
What happens: When m + n is odd, one half gets the extra value. (m + n + 1) // 2 puts it in the left half. So the median is max(left1, left2), which is what the code returns. (m + n) // 2 puts the extra value in the right half. The code still returns max(left1, left2), which is then the value just below the median.
Example: nums1 = [1, 3], nums2 = [2]
Mistake: returns 1.0Fix: returns 2.0

Earlier signals

Two sorted arrays must be combined (median, k-th element) without merging them.

Earlier invariant

i + j == half at every step, and the correct cut i always lies in [lo, hi].

Earlier direction

dual sequences ➔ cross-boundary bisection ➔ equilibrium cut

Earlier description

Earlier template

Python

1	from typing import List
2
3	def find_median_sorted_arrays(nums1: List[int], nums2: List[int]) -> float:
4	"""Median of Two Sorted Arrays: binary search on the cut in the shorter array.
5	Time: O(log(min(M, N))) \| Space: O(1)
6	"""
7	if len(nums1) > len(nums2):
8	nums1, nums2 = nums2, nums1 # Search strictly across shorter sequence
9
10	m, n = len(nums1), len(nums2)
11	half = (m + n + 1) // 2 # Size of the combined left half
12	lo, hi = 0, m
13
14	while lo <= hi:
15	i = lo + (hi - lo) // 2 # Cut in nums1
16	j = half - i # Matching cut in nums2
17
18	left1 = nums1[i - 1] if i > 0 else float('-inf')
19	right1 = nums1[i] if i < m else float('inf')
20	left2 = nums2[j - 1] if j > 0 else float('-inf')
21	right2 = nums2[j] if j < n else float('inf')
22
23	if left1 <= right2 and left2 <= right1: # Equilibrium verified
24	if (m + n) % 2 == 1:
25	return float(max(left1, left2))
26	return (max(left1, left2) + min(right1, right2)) / 2.0
27	elif left1 > right2:
28	hi = i - 1 # Cut i too far right
29	else:
30	lo = i + 1 # Cut i too far left
31
32	return 0.0

Earlier gotchas

Searching the longer array instead of the shorter one

Reading nums1[i - 1] when i == 0

Writing half = (m + n) // 2