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

P0MediumMental model~4 min speedrun

Lower Bound (First True Binary Search)

Grows into

Rotated Array Global Matrix Bisection Exact Match Feasible Function Extrema Search Kth Smallest Continuous Bisection

Unlocks

Upper Bound LIS Ordered Set Meet in the Middle Median of Two Sorted Arrays

The problem

Search Insert Position (LC 35)(opens leetcode.com)

You have an array of distinct integers in sorted order and a target value. If target is already in the array, return its index; otherwise, return the index it would land at if you inserted it while keeping the array sorted.

Solve it in O(log n) time.

Example 1

Input:nums = [1,3,5,6], target = 5

Output:2

Target 5 exists at index 2.

Lower Bound

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

Spot it when: The statement asks for the first position or version that passes a test, such as where target would be inserted in a sorted list (Search Insert Position (LC 35)), the first bad version (First Bad Version (LC 278)), or the first value that is at least target.

Lower Bound

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 before lo is False, and every candidate from hi on is True or does not exist, so the first True is always in [lo, hi].

is_feasible is False before the answer and True from the answer on, so one call at mid decides the move, which is hi = mid after a True and lo = mid + 1 after a False. A True mid may be the first True, so hi = mid keeps it in the range. A False mid is not the answer and the first True is to its right, so lo = mid + 1 drops it. After either move the first True is still in [lo, hi]. hi is allowed to be the answer, because it starts one past the last candidate, so a row with no True returns hi. The range gets smaller on every pass and lo never passes hi, so the loop stops with lo == hi, and lo is the answer. The trap is lo = mid in the False branch. The midpoint is rounded down, so when hi == lo + 1, mid equals lo. Then lo does not move, and the loop never ends.

See it run

Lower Bound, step by step

lo 0hi 6mid -

Each column is one index. T means True and F means False. The last column is hi at the start: one position after the last index, and it is never tested.

lo the left end of the range. Every candidate before lo is False.
hi the right end of the range. hi may be the answer, and it is never tested.
mid the candidate that this pass tests
mid = lo mid and lo are the same candidate
answer the first True, or hi when no index is True

Start: lo = 0 and hi = 6. The answer is somewhere from lo to hi, and hi is never tested.

nums[i]

1lo

endhi

at_least_target(i)

1 / 8

Gotchas1 of 7

The trap
Gotcha 1: Writing lo = mid instead of lo = mid + 1
Mistake
```
lo = mid
```
Fix
```
lo = mid + 1
```
What happens: When one candidate is left (hi is equal to lo + 1), mid equals lo. If the check is False there, lo = mid leaves lo where it was. The range never gets smaller, so the loop never ends.
Example: Search Insert Position (LC 35): nums = [1, 3, 5, 6], target = 5
Mistake: the loop never endsFix: returns 2
Gotcha 2: Writing hi = mid - 1 in the half-open template
Mistake
```
hi = mid - 1
```
Fix
```
hi = mid
```
What happens: The template keeps mid in the range when the check is True, because mid may be the first True. With hi = mid - 1, a True mid is dropped. For nums = [1, 3, 5, 6] and target = 5, the first pass has mid = 2, and nums[2] >= 5 is True. Then hi becomes 1, so index 2 leaves the range. The loop returns 1, but the insert position is 2.
Example: Search Insert Position (LC 35): nums = [1, 3, 5, 6], target = 5
Mistake: returns 1Fix: returns 2
Gotcha 3: Setting hi to the last index, not one past it
Mistake
```
binary_search_lower_bound(0, len(nums) - 1, is_feasible)
```
Fix
```
binary_search_lower_bound(0, len(nums), is_feasible)
```
What happens: The loop can return hi itself. For Search Insert Position (LC 35), hi = len(nums) means "insert at the very end". With hi = len(nums) - 1, that answer can't be returned. A target larger than every value then gets the last index instead.
Example: nums = [1, 3, 5, 6], target = 7
Mistake: returns 3Fix: returns 4
Gotcha 4: Reading nums[i] without checking i < len(nums)
Mistake
```
found = nums[i] == target
```
Fix
```
found = i < len(nums) and nums[i] == target
```
What happens: The search returns the first True, or hi when no candidate is True. That result is not always a valid index. When no value passes the check, the result is len(nums). Reading nums[len(nums)] raises an IndexError. Find First and Last Position of Element in Sorted Array (LC 34) needs this check before it returns the first index.
Example: nums = [1, 3, 5, 6], target = 7
Mistake: raises IndexErrorFix: returns False
Gotcha 5: Using a check that is not monotonic
Mistake
```
is_feasible = lambda i: nums[i] == target
```
Fix
```
is_feasible = lambda i: nums[i] >= target
```
What happens: Binary search needs every False before every True. nums[i] == target is True at one index and False on both sides of it. The search can then discard the half that holds the answer.
Example: nums = [1, 3, 5, 6], target = 3
Mistake: returns 4Fix: returns 1
Gotcha 6: Adding 1 to what bisect_left returns
Mistake
```
count = bisect.bisect_left(a, x) + 1
```
Fix
```
count = bisect.bisect_left(a, x)
```
What happens: bisect.bisect_left(a, x) runs this search on a sorted list a. It returns the first index i with a[i] >= x. Indices start at 0, so that index is also the number of values less than x. Adding 1 counts one value too many. bisect.bisect_right(a, x) counts the values less than or equal to x in the same way.
Example: a = [1, 2, 2, 3], x = 2
Mistake: returns 2Fix: returns 1
Gotcha 7: Forgetting + lo on the bisect form
Mistake
```
first = bisect.bisect_left(range(lo, hi), True, key=is_feasible)
```
Fix
```
first = bisect.bisect_left(range(lo, hi), True, key=is_feasible) + lo
```
What happens: bisect_left returns an offset in range(lo, hi), counted from 0. It does not return an index. When lo is not 0, the offset and the index differ by lo. For lo = 2 and hi = 6, the first True is index 4, which is offset 2 in the range. Without + lo, the answer is 2.
Example: lo = 2, hi = 6, and the check is True from index 4 on
Mistake: returns 2Fix: returns 4

Not this one if…

You only need to know whether target is present and any one index of it, as in Binary Search (LC 704), not where a yes/no check first becomes true. See Exact Match
There is no array of candidates to index: the answer is a value you choose (an eating speed) and checking it means simulating the whole input, as in Koko Eating Bananas (LC 875). See Feasible Function
The question asks for the largest value that still passes a check, as in Sqrt(x) (LC 69), the largest k with k * k <= x: the answer is the last True, not the first. See Upper Bound
The values are not sorted, as in H-Index (LC 274). H-Index II (LC 275) has sorted values and fits this card. With unsorted values there is no order to search, and sorting first costs more than counting. See Counting Sort

Theory

The question we build

What we know

nums is sorted, so nums[i] never gets smaller when i gets larger. One comparison at the middle index therefore shows which side can still hold the answer.

What the problem gives us

The input is nums and target. The loop needs two things built from them: a check for one index, and the range of candidate indices.

The question we build

We ask each index one yes-or-no question: "is nums[i] at least target?" The check at_least_target(i) returns nums[i] >= target. We use nums = [1, 3, 5, 6] and target = 5 (the first example of Search Insert Position (LC 35)). The answers are False, False, True, True. The values only get larger. So after one True, every later answer is True too.

nums[i]

at_least_target(i)

The first True is index 2, so target = 5 goes at index 2.

Narrowing down to the template

Every index before the insert position holds a value smaller than target. The insert position holds a value that is at least target. So the insert position is the first True of at_least_target. The candidates are the indices 0 to len(nums) - 1. So the call is binary_search_lower_bound(0, len(nums), at_least_target).

Step 1: Linear scan

The answer is the first index where the check is True. The scan finds it by checking the indices in order. It is correct, and it states in one line what the answer means.

Step 1: Linear scanPython

1		def first_true_scan(lo, hi, is_feasible):
2		i = lo
3		while i < hi and not is_feasible(i):
4		i += 1
5		return i # hi when no candidate is True

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

Step 2: Halving loop

The scan checks every candidate. The halving loop checks only mid, the middle of the range. The row of answers is False…False True…True, so one check at mid shows which side of mid cannot hold the first True. The loop discards that side, and the range is about half as long after every pass.

Step 2: Halving loopPython

1		def first_true_halving(lo, hi, is_feasible):
2		while lo < hi:
3		mid = lo + (hi - lo) // 2
4		if is_feasible(mid):
5		hi = mid # mid may be the first True: keep it
6		else:
7		lo = mid + 1 # mid is False: the first True is to the right
8		return lo

Cost: O(log N) checks.

Step 3: The named template

The loop does not change between problems. Only the check and the range change.

Step 3: The named templatePython

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

Cost: O(T * log N), where T is the cost of one is_feasible call.

Before	After	What changed
`def first_true_halving(lo, hi, is_feasible):`	`def binary_search_lower_bound(lo: int, hi: int, is_feasible: Callable[[int], bool]) -> int:`	A name and types. The loop is the same.
the loop body	the loop body	Identical. Only comments change.
(none)	the docstring	The contract is written down.

The shorter version

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

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

1		from bisect import bisect_left
2
3		# is_feasible must read False, then True.
4		first = bisect_left(range(lo, hi), True, key=is_feasible) + lo

bisect_left is Python's own version of this search. The key is_feasible turns each candidate into False or True, and bisect finds where True first appears. Bisect returns a position counted from 0 in the range, so add lo to get the candidate. For lo = 2, hi = 5 and a first True at candidate 3, bisect returns 1, and 1 + 2 = 3. When no candidate is True, the result is hi. An empty range also returns hi. Negative candidate values are allowed, because the position that bisect returns is never negative. Do not pass a negative lo to bisect itself: bisect_left(range(n), True, -1, hi, key=...) raises ValueError and does not count from the end. range does not build a list. The key= argument needs Python 3.10 or later.

2. A sorted list, nums

2. A sorted list, numsPython

1		from bisect import bisect_left
2
3		# nums is sorted; search indices in [lo, hi).
4		insert_at = bisect_left(nums, target, lo, hi)
5
6		# Records are sorted by their numeric first field.
7		records = [(1, 'Ada'), (2, 'Bo'), (2, 'Cy'), (4, 'Di')]
8		first_record = bisect_left(records, 2, 1, 4, key=lambda record: record[0]) # 1

bisect_left(nums, target, lo, hi) finds the first index in [lo, hi) where nums[i] >= target. The arguments are the list, the target, then the bounds. The result is already an index in nums, so do not add lo. If the target occurs in the window, the result is its first occurrence. Otherwise it is the insert position, and when no value qualifies it is hi. Indices start at 0, so for the whole list the result also equals the number of values below target. For nums = [1, 2, 2, 2, 4] and target = 2, the whole list gives 1, and the window lo = 2, hi = 5 gives 2. Check insert_at < hi before you read nums[insert_at].

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, and the first record with a key of at least 2 is at index 1. Before you index, check first_record < 4.

The range [lo, hi) and what hi means

The range [lo, hi) is called a half-open range. It includes lo and does not include hi. A closed range, written [lo, hi], includes both ends. In [lo, hi), hi is one past the last candidate, and the search never checks hi. Here are the candidates for nums = [1, 3, 5, 6]:

Index	0	1	2	3	4
Value	1	3	5	6	none
Role	candidate	candidate	candidate	candidate	`hi`, one past the last candidate

Because hi is never checked, it can stand for "no candidate is True". For Search Insert Position (LC 35), that answer means "insert at the end". Many books write the same search with a closed range: hi = len(nums) - 1 and while lo <= hi. That loop is in the "Old ways" tab.

The values you pass for lo and hi depend on what you look for. The template keeps one shape:

What you look for	`lo` (first candidate)	`hi` (one past the last candidate)
The first index with `nums[i] >= target`	`0`	`len(nums)`
The first bad version, with versions `1` to `n`	`1`	`n + 1`

How to build is_feasible

The check is the only part that changes between problems. Ask four questions, in this order:

What does True mean? Name it in words, for example at_least_target.
Is the row False…False True…True? 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. It is the answer when no candidate is True.

Here are three worked checks, each drawn on a tiny input. The first two use nums = [1, 3, 5, 6] and target = 3.

nums[i]

nums[i] >= target

nums[i] >= target is True from the first value that is at least target.

nums[i]

nums[i] > target

nums[i] > target is True from the first value that is larger than target.

version

is_bad_version(i)

First Bad Version (LC 278) with n = 5. Version 4 is the first bad version. The candidates are the versions 1 to n, so lo = 1 and hi = n + 1.

The contract

Item	Lower Bound
Range	Half-open `[lo, hi)`. `hi` is one past the last candidate.
Is `hi` checked?	Never. `mid < hi` on every pass.
The check	Takes one candidate. Returns `True` or `False`. Must be False…False True…True over `[lo, hi)`.
Returns	The first True. `hi` when no candidate is True.
Equal values	The first of them, because a True `mid` is kept and the search continues to the left.
Cost	`O(T * log N)` time and `O(1)` space. `N = hi - lo`, and `T` is the cost of one check.

A target smaller than every value needs no special case. Every check reads True, so each pass sets hi = mid. hi reaches lo, and the loop returns 0.

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

Real-world use

This search has standard-library names in several languages. Python's bisect.bisect_left runs this same half-open loop, and C++'s std::lower_bound returns the same position. Both find where a value belongs in a sorted sequence, for example to keep a list sorted while inserting.

Say it in an interview

About 60 seconds, for Search Insert Position (LC 35):

"I use Lower Bound, because the check nums[i] >= target is False, then True, so the insert position is the first True. I search [0, len(nums)), so len(nums) can mean insert at the end. A passing mid may be the answer, so hi = mid, and a failing mid is not, so lo = mid + 1. It takes O(log N) time and O(1) space. The trap is lo = mid. When hi == lo + 1, mid equals lo and the loop never ends."

Common Questions

How do you count how many times target appears?: Call Lower Bound twice: once with nums[i] >= target for the first index, and once with nums[i] > target for the first index after the equal values. The difference between the two results is the count. For nums = [1, 2, 2, 2, 4] and target = 2, the results are 1 and 4, so the count is 3.
How do you find the last index with nums[i] <= target using Lower Bound?: Find the first index where nums[i] > target, then subtract 1. For nums = [1, 2, 2, 2, 4] and target = 2, the first index with nums[i] > 2 is 4, so the answer is 3. When every value is greater than target, the first index is 0 and the answer is -1. Upper Bound returns the same value with one call.
Why does the loop not return when nums[mid] == target?: Equal values can repeat, and the answer is the first of them. A mid that equals target may have an equal value on its left, so the loop keeps mid with hi = mid and continues to the left. For nums = [2, 2, 2] and target = 2, the result is 0. An early return at the middle would give 1.

Practice

Canonical LeetCode:First Bad Version (LC 278)Search Insert Position (LC 35)Find First and Last Position of Element in Sorted Array (LC 34)Successful Pairs of Spells and Potions (LC 2300)Check If a Number Is Majority Element in a Sorted Array (LC 1150)Leftmost Column with at Least a One (LC 1428)Maximum Count of Positive Integer and Negative Integer (LC 2529)Fixed Point (LC 1064)Find K Closest Elements (LC 658)Single Element in a Sorted Array (LC 540)Count the Number of Fair Pairs (LC 2563)Longest Subsequence With Limited Sum (LC 2389)Ways to Split Array Into Three Subarrays (LC 1712)Missing Element in Sorted Array (LC 1060)Find Smallest Letter Greater Than Target (LC 744)H-Index II (LC 275)Time Based Key-Value Store (LC 981)Random Pick with Weight (LC 528)Random Point in Non-overlapping Rectangles (LC 497)

Most courses teach a new binary-search loop for every problem. This course teaches one loop, and each problem only changes the check that the loop calls.

The classic loop

Old Way

Python

1	from typing import List
2
3	def searchInsert(nums: List[int], target: int) -> int:
4	"""Search Insert Position, the classic closed loop.
5	Time: O(log N) \| Space: O(1)
6	"""
7	lo, hi = 0, len(nums) - 1
8	while lo <= hi:
9	mid = lo + (hi - lo) // 2
10	if nums[mid] >= target:
11	hi = mid - 1
12	else:
13	lo = mid + 1
14	return lo

Old Way, recording the answer

Python

1	def search_insert_recorded(nums, target, ans):
2	lo, hi = 0, len(nums) - 1
3	while lo <= hi:
4	mid = lo + (hi - lo) // 2
5	if nums[mid] >= target:
6	ans = mid
7	hi = mid - 1
8	else:
9	lo = mid + 1
10	return ans

From the classic loop to our template

Old Way line	In our template	Why
lo, hi = 0, len(nums) - 1	binary_search_lower_bound(0, len(nums), at_least_target)	The template's `hi` is one past the last index, so "no value passes" is the answer `hi`.
while lo <= hi:	while lo < hi:	The half-open range is empty when `lo` is equal to `hi`.
if nums[mid] >= target:	at_least_target(i): return nums[i] >= target	The question moves into a named check.
hi = mid - 1	hi = mid	The closed loop drops `mid`. In the template, `mid` can be the answer, so `hi = mid` keeps it, and no recorded answer is needed.
lo = mid + 1	lo = mid + 1	The same line in both forms.
return lo	insert_at = ..., then return insert_at	The result of the template call gets its own name.

When the classic form is fine

Use it when an interviewer asks for this form, or when the code base already uses it. The number of steps is about the same.

A second common form keeps the answer in a variable. Write ans = len(nums) before the loop, set ans = mid just before hi = mid - 1, and return ans. It is the same search.

Gotchas of the classic loop

Gotchas1 of 3

The trap
Gotcha 1: Writing hi = mid in the closed loop
Mistake
```
hi = mid
```
Fix
```
hi = mid - 1
```
What happens: The range [lo, hi] is closed, so mid is checked and then dropped. With hi = mid, the range keeps mid. When lo == hi and the check is True, hi does not move. lo <= hi stays True, so the loop never ends.
Example: nums = [1, 3, 5, 6], target = 5
Mistake: the loop never endsFix: returns 2
Gotcha 2: Starting ans at -1 instead of len(nums)
Mistake
```
ans = -1
```
Fix
```
ans = len(nums)
```
What happens: The recorded-answer form keeps the best index so far in ans. When target is larger than every value, the check is never True, so ans is never changed. The start value is then the answer. len(nums) is the right insert position. -1 is not an index at all.
Example: nums = [1, 3, 5, 6], target = 7
Mistake: returns -1Fix: returns 4
Gotcha 3: Looping while lo < hi in the closed loop
Mistake
```
while lo < hi:
```
Fix
```
while lo <= hi:
```
What happens: In the closed range [lo, hi], one candidate is still left when lo == hi. while lo < hi stops before it is checked. For target = 7, hi starts at 3 and lo reaches 3, so the loop stops with lo = 3. That is the index of the value 6, not the insert position 4.
Example: nums = [1, 3, 5, 6], target = 7
Mistake: returns 3Fix: returns 4

Earlier description

is_feasible is False for every candidate before the answer and True from the answer on, so mid only tells you which side of the flip you are on. If is_feasible(mid), mid may be the first True, so keep it with hi = mid; otherwise the first True is strictly to the right, so lo = mid + 1. The first True never leaves [lo, hi] (it is hi itself when nothing is True, since hi starts one past the last candidate), and the range shrinks on every step, so the loop stops at lo == hi on the answer. The trap is writing lo = mid in the False branch: with the floor midpoint, mid == lo when two candidates are left, so lo never moves and the loop never ends.

Earlier signals

The question is 'where does something first become true': insert position, first bad version, first value at least target, how many values are below a threshold.

Earlier invariant

Every candidate below lo is False and every candidate from hi on is True (or past the end), so the first True is always in [lo, hi].

Earlier gotchas

Reading nums[i] without checking i < len(nums)

The search returns a position, not an index that is known to be valid. When no value passes the check, it returns len(nums). Reading nums[len(nums)] raises an IndexError. Find First and Last Position of Element in Sorted Array (LC 34) needs this check before it returns the first position.

Earlier look-alikes

You only need to know whether target is present and any one index of it, as in Binary Search (LC 704), not where a yes/no check first turns true.
There is no array of candidates to index: the answer is a value you invent (an eating speed) and checking it means simulating the whole input, as in Koko Eating Bananas (LC 875).
The values are not sorted, as in H-Index (LC 274). It asks the same question as H-Index II (LC 275), but the citations are not sorted. There is no order to binary search, and sorting first costs more than counting the papers for each citation value.

Earlier template

Python

1	from typing import Callable
2
3	def binary_search_lower_bound(lo: int, hi: int, is_feasible: Callable[[int], bool]) -> int:
4	"""First Bad Version / Search Insert Position: first candidate in [lo, hi) where is_feasible is True.
5	Precondition: is_feasible is monotonic (False, False, ..., True, True).
6	Returns hi when no candidate is True. N = hi - lo candidates.
7	Time: O(log N) \| Space: O(1)
8	"""
9	while lo < hi:
10	mid = lo + (hi - lo) // 2
11	if is_feasible(mid):
12	hi = mid # Preserve mid as candidate; search left
13	else:
14	lo = mid + 1 # Discard mid; first true must be strictly right
15
16	return lo # lo == hi is the exact boundary

Earlier problems

Is Subsequence

Theory Context•Binary Search Boundary

P0MediumMental model~4 min speedrun

Lower Bound (First True Binary Search)

Grows into

Rotated Array Global Matrix Bisection Exact Match Feasible Function Extrema Search Kth Smallest Continuous Bisection

Unlocks

Upper Bound LIS Ordered Set Meet in the Middle Median of Two Sorted Arrays

The problem

Search Insert Position (LC 35)(opens leetcode.com)

Solve it in O(log n) time.

Example 1

Input:nums = [1,3,5,6], target = 5

Output:2

Target 5 exists at index 2.

Lower Bound

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

Lower Bound

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 before lo is False, and every candidate from hi on is True or does not exist, so the first True is always in [lo, hi].

See it run

Lower Bound, step by step

lo 0hi 6mid -

Each column is one index. T means True and F means False. The last column is hi at the start: one position after the last index, and it is never tested.

lo the left end of the range. Every candidate before lo is False.
hi the right end of the range. hi may be the answer, and it is never tested.
mid the candidate that this pass tests
mid = lo mid and lo are the same candidate
answer the first True, or hi when no index is True

Start: lo = 0 and hi = 6. The answer is somewhere from lo to hi, and hi is never tested.

nums[i]

1lo

endhi

at_least_target(i)

1 / 8

Gotchas1 of 7

The trap
Gotcha 1: Writing lo = mid instead of lo = mid + 1
Mistake
```
lo = mid
```
Fix
```
lo = mid + 1
```
What happens: When one candidate is left (hi is equal to lo + 1), mid equals lo. If the check is False there, lo = mid leaves lo where it was. The range never gets smaller, so the loop never ends.
Example: Search Insert Position (LC 35): nums = [1, 3, 5, 6], target = 5
Mistake: the loop never endsFix: returns 2
Gotcha 2: Writing hi = mid - 1 in the half-open template
Mistake
```
hi = mid - 1
```
Fix
```
hi = mid
```
What happens: The template keeps mid in the range when the check is True, because mid may be the first True. With hi = mid - 1, a True mid is dropped. For nums = [1, 3, 5, 6] and target = 5, the first pass has mid = 2, and nums[2] >= 5 is True. Then hi becomes 1, so index 2 leaves the range. The loop returns 1, but the insert position is 2.
Example: Search Insert Position (LC 35): nums = [1, 3, 5, 6], target = 5
Mistake: returns 1Fix: returns 2
Gotcha 3: Setting hi to the last index, not one past it
Mistake
```
binary_search_lower_bound(0, len(nums) - 1, is_feasible)
```
Fix
```
binary_search_lower_bound(0, len(nums), is_feasible)
```
What happens: The loop can return hi itself. For Search Insert Position (LC 35), hi = len(nums) means "insert at the very end". With hi = len(nums) - 1, that answer can't be returned. A target larger than every value then gets the last index instead.
Example: nums = [1, 3, 5, 6], target = 7
Mistake: returns 3Fix: returns 4
Gotcha 4: Reading nums[i] without checking i < len(nums)
Mistake
```
found = nums[i] == target
```
Fix
```
found = i < len(nums) and nums[i] == target
```
What happens: The search returns the first True, or hi when no candidate is True. That result is not always a valid index. When no value passes the check, the result is len(nums). Reading nums[len(nums)] raises an IndexError. Find First and Last Position of Element in Sorted Array (LC 34) needs this check before it returns the first index.
Example: nums = [1, 3, 5, 6], target = 7
Mistake: raises IndexErrorFix: returns False
Gotcha 5: Using a check that is not monotonic
Mistake
```
is_feasible = lambda i: nums[i] == target
```
Fix
```
is_feasible = lambda i: nums[i] >= target
```
What happens: Binary search needs every False before every True. nums[i] == target is True at one index and False on both sides of it. The search can then discard the half that holds the answer.
Example: nums = [1, 3, 5, 6], target = 3
Mistake: returns 4Fix: returns 1
Gotcha 6: Adding 1 to what bisect_left returns
Mistake
```
count = bisect.bisect_left(a, x) + 1
```
Fix
```
count = bisect.bisect_left(a, x)
```
What happens: bisect.bisect_left(a, x) runs this search on a sorted list a. It returns the first index i with a[i] >= x. Indices start at 0, so that index is also the number of values less than x. Adding 1 counts one value too many. bisect.bisect_right(a, x) counts the values less than or equal to x in the same way.
Example: a = [1, 2, 2, 3], x = 2
Mistake: returns 2Fix: returns 1
Gotcha 7: Forgetting + lo on the bisect form
Mistake
```
first = bisect.bisect_left(range(lo, hi), True, key=is_feasible)
```
Fix
```
first = bisect.bisect_left(range(lo, hi), True, key=is_feasible) + lo
```
What happens: bisect_left returns an offset in range(lo, hi), counted from 0. It does not return an index. When lo is not 0, the offset and the index differ by lo. For lo = 2 and hi = 6, the first True is index 4, which is offset 2 in the range. Without + lo, the answer is 2.
Example: lo = 2, hi = 6, and the check is True from index 4 on
Mistake: returns 2Fix: returns 4

Not this one if…

You only need to know whether target is present and any one index of it, as in Binary Search (LC 704), not where a yes/no check first becomes true. See Exact Match
There is no array of candidates to index: the answer is a value you choose (an eating speed) and checking it means simulating the whole input, as in Koko Eating Bananas (LC 875). See Feasible Function
The question asks for the largest value that still passes a check, as in Sqrt(x) (LC 69), the largest k with k * k <= x: the answer is the last True, not the first. See Upper Bound
The values are not sorted, as in H-Index (LC 274). H-Index II (LC 275) has sorted values and fits this card. With unsorted values there is no order to search, and sorting first costs more than counting. See Counting Sort

Theory

The question we build

What we know

nums is sorted, so nums[i] never gets smaller when i gets larger. One comparison at the middle index therefore shows which side can still hold the answer.

What the problem gives us

The input is nums and target. The loop needs two things built from them: a check for one index, and the range of candidate indices.

The question we build

nums[i]

at_least_target(i)

The first True is index 2, so target = 5 goes at index 2.

Narrowing down to the template

Step 1: Linear scan

The answer is the first index where the check is True. The scan finds it by checking the indices in order. It is correct, and it states in one line what the answer means.

Step 1: Linear scanPython

1		def first_true_scan(lo, hi, is_feasible):
2		i = lo
3		while i < hi and not is_feasible(i):
4		i += 1
5		return i # hi when no candidate is True

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

Step 2: Halving loop

Step 2: Halving loopPython

1		def first_true_halving(lo, hi, is_feasible):
2		while lo < hi:
3		mid = lo + (hi - lo) // 2
4		if is_feasible(mid):
5		hi = mid # mid may be the first True: keep it
6		else:
7		lo = mid + 1 # mid is False: the first True is to the right
8		return lo

Cost: O(log N) checks.

Step 3: The named template

The loop does not change between problems. Only the check and the range change.

Step 3: The named templatePython

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

Cost: O(T * log N), where T is the cost of one is_feasible call.

Before	After	What changed
`def first_true_halving(lo, hi, is_feasible):`	`def binary_search_lower_bound(lo: int, hi: int, is_feasible: Callable[[int], bool]) -> int:`	A name and types. The loop is the same.
the loop body	the loop body	Identical. Only comments change.
(none)	the docstring	The contract is written down.

The shorter version

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

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

1		from bisect import bisect_left
2
3		# is_feasible must read False, then True.
4		first = bisect_left(range(lo, hi), True, key=is_feasible) + lo

2. A sorted list, nums

2. A sorted list, numsPython

1		from bisect import bisect_left
2
3		# nums is sorted; search indices in [lo, hi).
4		insert_at = bisect_left(nums, target, lo, hi)
5
6		# Records are sorted by their numeric first field.
7		records = [(1, 'Ada'), (2, 'Bo'), (2, 'Cy'), (4, 'Di')]
8		first_record = bisect_left(records, 2, 1, 4, key=lambda record: record[0]) # 1

The range [lo, hi) and what hi means

Index	0	1	2	3	4
Value	1	3	5	6	none
Role	candidate	candidate	candidate	candidate	`hi`, one past the last candidate

The values you pass for lo and hi depend on what you look for. The template keeps one shape:

What you look for	`lo` (first candidate)	`hi` (one past the last candidate)
The first index with `nums[i] >= target`	`0`	`len(nums)`
The first bad version, with versions `1` to `n`	`1`	`n + 1`

How to build is_feasible

The check is the only part that changes between problems. Ask four questions, in this order:

What does True mean? Name it in words, for example at_least_target.
Is the row False…False True…True? 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. It is the answer when no candidate is True.

Here are three worked checks, each drawn on a tiny input. The first two use nums = [1, 3, 5, 6] and target = 3.

nums[i]

nums[i] >= target

nums[i] >= target is True from the first value that is at least target.

nums[i]

nums[i] > target

nums[i] > target is True from the first value that is larger than target.

version

is_bad_version(i)

First Bad Version (LC 278) with n = 5. Version 4 is the first bad version. The candidates are the versions 1 to n, so lo = 1 and hi = n + 1.

The contract

Item	Lower Bound
Range	Half-open `[lo, hi)`. `hi` is one past the last candidate.
Is `hi` checked?	Never. `mid < hi` on every pass.
The check	Takes one candidate. Returns `True` or `False`. Must be False…False True…True over `[lo, hi)`.
Returns	The first True. `hi` when no candidate is True.
Equal values	The first of them, because a True `mid` is kept and the search continues to the left.
Cost	`O(T * log N)` time and `O(1)` space. `N = hi - lo`, and `T` is the cost of one check.

A target smaller than every value needs no special case. Every check reads True, so each pass sets hi = mid. hi reaches lo, and the loop returns 0.

Real-world use

Say it in an interview

About 60 seconds, for Search Insert Position (LC 35):

"I use Lower Bound, because the check nums[i] >= target is False, then True, so the insert position is the first True. I search [0, len(nums)), so len(nums) can mean insert at the end. A passing mid may be the answer, so hi = mid, and a failing mid is not, so lo = mid + 1. It takes O(log N) time and O(1) space. The trap is lo = mid. When hi == lo + 1, mid equals lo and the loop never ends."

Common Questions

How do you count how many times target appears?: Call Lower Bound twice: once with nums[i] >= target for the first index, and once with nums[i] > target for the first index after the equal values. The difference between the two results is the count. For nums = [1, 2, 2, 2, 4] and target = 2, the results are 1 and 4, so the count is 3.
How do you find the last index with nums[i] <= target using Lower Bound?: Find the first index where nums[i] > target, then subtract 1. For nums = [1, 2, 2, 2, 4] and target = 2, the first index with nums[i] > 2 is 4, so the answer is 3. When every value is greater than target, the first index is 0 and the answer is -1. Upper Bound returns the same value with one call.
Why does the loop not return when nums[mid] == target?: Equal values can repeat, and the answer is the first of them. A mid that equals target may have an equal value on its left, so the loop keeps mid with hi = mid and continues to the left. For nums = [2, 2, 2] and target = 2, the result is 0. An early return at the middle would give 1.

Practice

Most courses teach a new binary-search loop for every problem. This course teaches one loop, and each problem only changes the check that the loop calls.

The classic loop

Old Way

Python

1	from typing import List
2
3	def searchInsert(nums: List[int], target: int) -> int:
4	"""Search Insert Position, the classic closed loop.
5	Time: O(log N) \| Space: O(1)
6	"""
7	lo, hi = 0, len(nums) - 1
8	while lo <= hi:
9	mid = lo + (hi - lo) // 2
10	if nums[mid] >= target:
11	hi = mid - 1
12	else:
13	lo = mid + 1
14	return lo

Old Way, recording the answer

Python

1	def search_insert_recorded(nums, target, ans):
2	lo, hi = 0, len(nums) - 1
3	while lo <= hi:
4	mid = lo + (hi - lo) // 2
5	if nums[mid] >= target:
6	ans = mid
7	hi = mid - 1
8	else:
9	lo = mid + 1
10	return ans

From the classic loop to our template

Old Way line	In our template	Why
lo, hi = 0, len(nums) - 1	binary_search_lower_bound(0, len(nums), at_least_target)	The template's `hi` is one past the last index, so "no value passes" is the answer `hi`.
while lo <= hi:	while lo < hi:	The half-open range is empty when `lo` is equal to `hi`.
if nums[mid] >= target:	at_least_target(i): return nums[i] >= target	The question moves into a named check.
hi = mid - 1	hi = mid	The closed loop drops `mid`. In the template, `mid` can be the answer, so `hi = mid` keeps it, and no recorded answer is needed.
lo = mid + 1	lo = mid + 1	The same line in both forms.
return lo	insert_at = ..., then return insert_at	The result of the template call gets its own name.

When the classic form is fine

Use it when an interviewer asks for this form, or when the code base already uses it. The number of steps is about the same.

A second common form keeps the answer in a variable. Write ans = len(nums) before the loop, set ans = mid just before hi = mid - 1, and return ans. It is the same search.

Gotchas of the classic loop

Gotchas1 of 3

The trap
Gotcha 1: Writing hi = mid in the closed loop
Mistake
```
hi = mid
```
Fix
```
hi = mid - 1
```
What happens: The range [lo, hi] is closed, so mid is checked and then dropped. With hi = mid, the range keeps mid. When lo == hi and the check is True, hi does not move. lo <= hi stays True, so the loop never ends.
Example: nums = [1, 3, 5, 6], target = 5
Mistake: the loop never endsFix: returns 2
Gotcha 2: Starting ans at -1 instead of len(nums)
Mistake
```
ans = -1
```
Fix
```
ans = len(nums)
```
What happens: The recorded-answer form keeps the best index so far in ans. When target is larger than every value, the check is never True, so ans is never changed. The start value is then the answer. len(nums) is the right insert position. -1 is not an index at all.
Example: nums = [1, 3, 5, 6], target = 7
Mistake: returns -1Fix: returns 4
Gotcha 3: Looping while lo < hi in the closed loop
Mistake
```
while lo < hi:
```
Fix
```
while lo <= hi:
```
What happens: In the closed range [lo, hi], one candidate is still left when lo == hi. while lo < hi stops before it is checked. For target = 7, hi starts at 3 and lo reaches 3, so the loop stops with lo = 3. That is the index of the value 6, not the insert position 4.
Example: nums = [1, 3, 5, 6], target = 7
Mistake: returns 3Fix: returns 4

Earlier description

Earlier signals

The question is 'where does something first become true': insert position, first bad version, first value at least target, how many values are below a threshold.

Earlier invariant

Every candidate below lo is False and every candidate from hi on is True (or past the end), so the first True is always in [lo, hi].

Earlier gotchas

Reading nums[i] without checking i < len(nums)

Earlier look-alikes

You only need to know whether target is present and any one index of it, as in Binary Search (LC 704), not where a yes/no check first turns true.
There is no array of candidates to index: the answer is a value you invent (an eating speed) and checking it means simulating the whole input, as in Koko Eating Bananas (LC 875).
The values are not sorted, as in H-Index (LC 274). It asks the same question as H-Index II (LC 275), but the citations are not sorted. There is no order to binary search, and sorting first costs more than counting the papers for each citation value.

Earlier template

Python

1	from typing import Callable
2
3	def binary_search_lower_bound(lo: int, hi: int, is_feasible: Callable[[int], bool]) -> int:
4	"""First Bad Version / Search Insert Position: first candidate in [lo, hi) where is_feasible is True.
5	Precondition: is_feasible is monotonic (False, False, ..., True, True).
6	Returns hi when no candidate is True. N = hi - lo candidates.
7	Time: O(log N) \| Space: O(1)
8	"""
9	while lo < hi:
10	mid = lo + (hi - lo) // 2
11	if is_feasible(mid):
12	hi = mid # Preserve mid as candidate; search left
13	else:
14	lo = mid + 1 # Discard mid; first true must be strictly right
15
16	return lo # lo == hi is the exact boundary

Earlier problems

Is Subsequence