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

The entire core curriculum of 12 patterns and 180 archetypes is 100% free to access with no credit card required. Students receive 40 free compute coins upon registration, +20 daily login coins, and +25 referral coins. A 24-hour unlimited AI coaching pass costs only 5 coins. Alternatively, developers can use Bring-Your-Own-Key (BYOK) for completely free unlimited AI coaching with personal Gemini or OpenAI keys. There are no recurring subscription fees.

What is the refund and cancellation policy?

Hi👋SpeedAlgo has zero recurring subscriptions, zero automatic renewals, and zero hidden billing traps. Because the core platform and learning materials are free, students never face unwanted credit card charges or recurring payment obligations.

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 enforces deliberate practice: proving invariants, articulating Big-O tradeoffs, managing edge cases, and defending algorithmic approaches to a Senior SWE AI Mock Coach in an integrated Monaco code editor.

12. Flattened Matrix Search: Search a 2D Matrix (LC 74) • Invariant Proof & Speed-Run

Theory Context•Binary Search Boundary

MediumLC 74

Search a 2D Matrix (LeetCode 74)

You will see why a matrix whose rows continue one another is really one sorted list, and how to binary search it without copying it.

Target Frequency:AmazonMicrosoftBloomberg

You're given an m x n grid of integers, matrix, with two guarantees: each row is sorted left-to-right (non-decreasing), and every row's first value is bigger than the previous row's last value — so reading the grid row by row, the numbers only ever increase.

Given a target value, decide whether it appears anywhere in matrix.

Your solution must run in O(log(m * n)) time.

Worked Examples

Example 1

Input:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3

Output:true

Explanation: Read row by row, the grid is `1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60`; `3` is there, at `matrix[0][1]`.

Example 2

Input:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13

Output:false

Explanation: `13` would fall between `11` and `16` in the second row, and it is not in the grid.

⚖️Formal Constraints & Bounds

m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-10⁴ <= matrix[i][j], target <= 10⁴

Deep-Dive & Conceptual Insights

Why It Works & Core Invariant

Reading row by row gives one sorted list, and position mid of that list is matrix[mid // n][mid % n]: binary search the positions and never build the list.

Real-World Scenario & Production Applications

Fixed-size pages: a sorted log split into pages of n records stores record k on page k // n at slot k % n. Looking a key up means binary searching record numbers and reading only the pages the probes land on, never loading the whole log into one array.

Step-by-Step Execution Trace Table

Step	`[lo, hi]`	`mid`	`row, col = divmod(mid, 4)`	`val`	Compare with `3`	Action
1	`[0, 11]`	5	`(1, 1)`	11	`11 > 3`	`hi = mid - 1 = 4`
2	`[0, 4]`	2	`(0, 2)`	5	`5 > 3`	`hi = mid - 1 = 1`
3	`[0, 1]`	0	`(0, 0)`	1	`1 < 3`	`lo = mid + 1 = 1`
4	`[1, 1]`	1	`(0, 1)`	3	`3 == 3`	Return `True`

Scroll horizontally to see all columns, or expand to full screen

Core Invariant Specification & Code Shape

Archetype Code Shape

Python

1	Read row by row, `matrix` is one sorted list of `m * n` values, because every row starts after the previous row ends: binary search that list's positions without building it.
2	Keep the closed range `[lo, hi]` of flat indices that can still hold `target`. Compare `val` with `target`: equal returns `True`; otherwise drop `mid` and the half that cannot hold it.
3	`m, n = len(matrix), len(matrix[0])`; `lo, hi = 0, m * n - 1`; `while lo <= hi:` take `mid = lo + (hi - lo) // 2`, turn it into `row, col`, read `val = matrix[row][col]`, then branch; `return False` after the loop.
4	The trap: `row, col = divmod(mid, n)` divides by `n`, the number of columns. `divmod(mid, m)` works on a square matrix and reads the wrong cell on every other shape.

Target: Search a 2D Matrix (LeetCode 74). The sorted list is every cell in reading order, so the closed range covers flat indices 0 to m * n - 1.

Boundary Model: Closed Candidate Interval [L, R]

Both L and R are inclusive valid indices. When condition matches or fails, candidate space shrinks by setting lo = mid + 1 or hi = mid - 1 symmetrically.

Loop Invariant Termination

while (lo <= hi) with mid = lo + (hi - lo) // 2.

Conceptual Narrative

🧭 Conceptual Foundation & Pattern Intuition

matrix looks two-dimensional, but its sort order is one-dimensional: each row is sorted, and each row starts after the previous row ends, so reading the rows one after another gives a single sorted list of m * n values. Classic Binary Search needs nothing more than a sorted list it can index. So search the positions of that list, 0 to m * n - 1, and never build it: each time you need the value at position mid, work out which cell holds it.

🏟️ The Analogy: Numbered Seats in a Theater

A theater numbers its seats 0, 1, 2, ... row by row, n seats to a row. In a theater with 10 seats per row, seat number 17 is in row 17 // 10 = 1, place 17 % 10 = 7. The usher never lines everyone up in one long queue to find it; they divide by the number of seats in a row. The number of rows never enters the formula: a theater with 3 rows or 30 rows puts seat 17 in the same place.

🪄 The Mathematical Harmony / Magic Trick

Code / Blueprint

m, n = len(matrix), len(matrix[0])
lo, hi = 0, m * n - 1          # every cell, as one sorted list
while lo <= hi:
    mid = lo + (hi - lo) // 2
    row, col = divmod(mid, n)  # mid // n full rows come first; mid % n is the place in the row
    val = matrix[row][col]
    ...

Position mid has exactly mid // n complete rows in front of it, and it is mid % n cells into its own row, so matrix[row][col] is the value the flat list would hold at mid. From there it is Classic Binary Search unchanged: the closed range [lo, hi], while lo <= hi, and lo = mid + 1 or hi = mid - 1.

💡 Summary

Treat the matrix as one sorted list of m * n values, binary search its positions, and translate each mid with divmod(mid, n), dividing by the number of columns, never the number of rows. One loop, $O(\log(m \cdot n))$ time, $O(1)$ space.

Dividing by the row count: row, col = divmod(mid, n) divides by n, the number of columns. On a 3 x 4 matrix flat index 5 is matrix[1][1], but divmod(5, 3) reads matrix[1][2], and divmod(11, 3) asks for a fourth row that does not exist. A square matrix hides this bug, so test a non-square one.
hi = m * n: the last flat index is m * n - 1. With hi = m * n the closed range [lo, hi] can read one cell past the end of the matrix.
Picking the row first: a binary search down the first column to choose the row, then one inside that row, also meets the bound, but choosing the row is a lower-bound search with its own off-by-one (a target below matrix[0][0] has no row). One search on the flat index has no row step to get wrong.
Walking from a corner: the staircase walk (start top-right, drop a row or a column per comparison) is correct but takes O(m + n) steps, too slow for the required O(log(m * n)).

Senior SWE Reasoning Architecture

4-Phase Thought Process Model

You will see how a senior engineer spots one sorted list inside a grid and says so out loud.

Pattern Recognition Signals

The 10-second spot

"Every row's first value is bigger than the previous row's last value" means the grid, read row by row, is one sorted list; "must run in O(log(m * n)) time" rules out walking from a corner. A sorted list with a log-time requirement is Classic Binary Search, here on flat indices.

Formulating the Predicate & Invariants

Turning intuition into a boolean rule

If target is in matrix, its flat index is inside [lo, hi]. Flat index mid is matrix[row][col] with row, col = divmod(mid, n); comparing val with target drops mid and the half that cannot hold it (lo = mid + 1 or hi = mid - 1).

Silent Failure Traps & Edge Cases

Where confident candidates still lose points

row, col = divmod(mid, n) divides by n, the number of columns, not m: on the 3 x 4 example flat index 5 is matrix[1][1] = 11, while divmod(5, 3) reads matrix[1][2] = 16, and divmod(11, 3) asks for a fourth row. A square matrix hides the bug.
hi = m * n - 1, the last flat index: hi = m * n lets the closed range read past the end.
while lo <= hi, not <: the last remaining flat index must still be read (a 1 x 1 matrix would otherwise never be checked).
Picking the row first with a search down column 0 adds a lower-bound step with its own off-by-one; the flat index needs one loop.

The 60-Second Interview Pitch

Say this out loud before you type a single line

I'd solve this with Flattened Matrix Search: a flat index. Every row starts after the previous row ends, so reading the grid row by row gives one sorted list of m times n values, and I run a normal binary search over positions zero to m times n minus one without copying anything. For each mid I find the cell with divmod of mid by n: mid over n full rows come before it, and mid mod n is where it sits in its row. Then it's the usual three-way compare: return true on a match, otherwise move lo past mid or hi below it. The trap I avoid is dividing by m, the number of rows: a square test hides it, but on a three by four grid it reads the wrong cell. That's O(log(m times n)) time and O(1) space.

So: name the flat index, divide by the number of columns, and run Classic Binary Search unchanged.

Big-O Invariant Derivation

Complexity & Mathematical Proof

TIME COMPLEXITY

O(log(M * N))

Look at the code: lo, hi = 0, m * n - 1 starts with all M * N flat positions. Each pass of while lo <= hi does one divmod, one read of matrix[row][col] and one comparison, then drops mid and one half with lo = mid + 1 or hi = mid - 1. The range shrinks M·N → M·N/2 → ... → 1, so there are at most floor(log2(M·N)) + 1 passes of constant work: O(log(M * N)).

SPACE COMPLEXITY

O(1)

The code keeps m, n, lo, hi, mid, row, col and val, whatever the matrix size, and returns one boolean. It never builds the flat list, so the extra space is O(1).

Formal Recurrence Relation

T(M·N) = T(M·N / 2) + O(1) = O(log(M * N))

Derivation Progression

Setup

O(1)

m, n = len(matrix), len(matrix[0]) and lo, hi = 0, m * n - 1 are constant work.

Halving loop

at most floor(log2(M·N)) + 1 passes

Each pass of while lo <= hi removes mid and one half of [lo, hi].

One probe

O(1) per pass

divmod(mid, n), one read matrix[row][col] and one comparison, whatever M and N are.

Total

O(log(M * N))

Constant work times a logarithmic number of passes.

Variable Definitions

$M$

Number of rows, len(matrix)

$N$

Number of columns, len(matrix[0])

$mid$

The flat index being probed, a position in the row-by-row list

Memory Architecture & Bounds

🟣 Call Stack

O(1) Iterative, no recursion

🔵 Auxiliary Heap

O(1): m, n, lo, hi, mid, row, col, val; no flattened copy

🟢 Output Space

O(1): one boolean

Boundary Best / Worst Cases

Best Case

$O(1)$ : target is at the first mid

Average Case

$O(\log(M \cdot N))$

Worst Case

$O(\log(M \cdot N))$ : target is absent or found on the last probe

Pointer Invariant Transition Progression

Synthesizing vector architecture diagram...

Staff+ Engineering Perspective

Senior SWE Deconstruction & Hardware Caveats

ARCHITECTURAL SIGNALS & INTERVIEW TRIGGERS

Triggers: "every row's first value is bigger than the previous row's last value" and **"must run in O(log(m * n)) time"**. The grid is one sorted list stored row by row, so the move is Flattened Matrix Search: Classic Binary Search on the flat index, translated with row, col = divmod(mid, n).

CONSTRAINTS & BOUNDS

$m, n \le 100$ , so at most $10^4$ cells and about 14 probes. Budget: $O(\log(m \cdot n))$ time, $O(1)$ space. For grids with more than $2^{31}$ cells the flat index needs a 64-bit integer in Java, C# or C++.

FAANG PRODUCTION TRAPS & EDGE CASES

Copying the grid into one list first costs $O(m \cdot n)$ time and memory and throws the log bound away. When each row is a separate page or block in storage, every probe may be a separate read, so the probe count, about $\log_2(m \cdot n)$ , is what the design must keep small; fetch only the probed rows.

Core Algorithmic State Invariants

1. One Sorted List

Each row is sorted and starts after the previous row ends, so `matrix` read row by row is one sorted list of `m * n` values. Classic Binary Search needs nothing more.

2. Flat Index to Cell

Position `mid` has `mid // n` full rows before it and is `mid % n` cells into its row: `row, col = divmod(mid, n)`. The divisor is the row length `n`, never the row count `m`.

3. Closed Range, Logarithmic Probes

`[lo, hi]` starts at `[0, m * n - 1]` and every comparison drops `mid` and one half: at most about log2(m * n) + 1 probes, O(1) space, and the matrix is never copied.

Theory Context•Binary Search Boundary

MediumLC 74

Search a 2D Matrix (LeetCode 74)

You will see why a matrix whose rows continue one another is really one sorted list, and how to binary search it without copying it.

Target Frequency:AmazonMicrosoftBloomberg

Given a target value, decide whether it appears anywhere in matrix.

Your solution must run in O(log(m * n)) time.

Worked Examples

Example 1

Input:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3

Output:true

Explanation: Read row by row, the grid is `1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60`; `3` is there, at `matrix[0][1]`.

Example 2

Input:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13

Output:false

Explanation: `13` would fall between `11` and `16` in the second row, and it is not in the grid.

⚖️Formal Constraints & Bounds

m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-10⁴ <= matrix[i][j], target <= 10⁴

Deep-Dive & Conceptual Insights

Why It Works & Core Invariant

Reading row by row gives one sorted list, and position mid of that list is matrix[mid // n][mid % n]: binary search the positions and never build the list.

Real-World Scenario & Production Applications

Step-by-Step Execution Trace Table

Step	`[lo, hi]`	`mid`	`row, col = divmod(mid, 4)`	`val`	Compare with `3`	Action
1	`[0, 11]`	5	`(1, 1)`	11	`11 > 3`	`hi = mid - 1 = 4`
2	`[0, 4]`	2	`(0, 2)`	5	`5 > 3`	`hi = mid - 1 = 1`
3	`[0, 1]`	0	`(0, 0)`	1	`1 < 3`	`lo = mid + 1 = 1`
4	`[1, 1]`	1	`(0, 1)`	3	`3 == 3`	Return `True`

Scroll horizontally to see all columns, or expand to full screen

Core Invariant Specification & Code Shape

Archetype Code Shape

Python

1	Read row by row, `matrix` is one sorted list of `m * n` values, because every row starts after the previous row ends: binary search that list's positions without building it.
2	Keep the closed range `[lo, hi]` of flat indices that can still hold `target`. Compare `val` with `target`: equal returns `True`; otherwise drop `mid` and the half that cannot hold it.
3	`m, n = len(matrix), len(matrix[0])`; `lo, hi = 0, m * n - 1`; `while lo <= hi:` take `mid = lo + (hi - lo) // 2`, turn it into `row, col`, read `val = matrix[row][col]`, then branch; `return False` after the loop.
4	The trap: `row, col = divmod(mid, n)` divides by `n`, the number of columns. `divmod(mid, m)` works on a square matrix and reads the wrong cell on every other shape.

Target: Search a 2D Matrix (LeetCode 74). The sorted list is every cell in reading order, so the closed range covers flat indices 0 to m * n - 1.

Boundary Model: Closed Candidate Interval [L, R]

Both L and R are inclusive valid indices. When condition matches or fails, candidate space shrinks by setting lo = mid + 1 or hi = mid - 1 symmetrically.

Loop Invariant Termination

while (lo <= hi) with mid = lo + (hi - lo) // 2.

Conceptual Narrative

🧭 Conceptual Foundation & Pattern Intuition

🏟️ The Analogy: Numbered Seats in a Theater

🪄 The Mathematical Harmony / Magic Trick

Code / Blueprint

m, n = len(matrix), len(matrix[0])
lo, hi = 0, m * n - 1          # every cell, as one sorted list
while lo <= hi:
    mid = lo + (hi - lo) // 2
    row, col = divmod(mid, n)  # mid // n full rows come first; mid % n is the place in the row
    val = matrix[row][col]
    ...

💡 Summary

Dividing by the row count: row, col = divmod(mid, n) divides by n, the number of columns. On a 3 x 4 matrix flat index 5 is matrix[1][1], but divmod(5, 3) reads matrix[1][2], and divmod(11, 3) asks for a fourth row that does not exist. A square matrix hides this bug, so test a non-square one.
hi = m * n: the last flat index is m * n - 1. With hi = m * n the closed range [lo, hi] can read one cell past the end of the matrix.
Picking the row first: a binary search down the first column to choose the row, then one inside that row, also meets the bound, but choosing the row is a lower-bound search with its own off-by-one (a target below matrix[0][0] has no row). One search on the flat index has no row step to get wrong.
Walking from a corner: the staircase walk (start top-right, drop a row or a column per comparison) is correct but takes O(m + n) steps, too slow for the required O(log(m * n)).

Senior SWE Reasoning Architecture

4-Phase Thought Process Model

You will see how a senior engineer spots one sorted list inside a grid and says so out loud.

Pattern Recognition Signals

The 10-second spot

Formulating the Predicate & Invariants

Turning intuition into a boolean rule

Silent Failure Traps & Edge Cases

Where confident candidates still lose points

row, col = divmod(mid, n) divides by n, the number of columns, not m: on the 3 x 4 example flat index 5 is matrix[1][1] = 11, while divmod(5, 3) reads matrix[1][2] = 16, and divmod(11, 3) asks for a fourth row. A square matrix hides the bug.
hi = m * n - 1, the last flat index: hi = m * n lets the closed range read past the end.
while lo <= hi, not <: the last remaining flat index must still be read (a 1 x 1 matrix would otherwise never be checked).
Picking the row first with a search down column 0 adds a lower-bound step with its own off-by-one; the flat index needs one loop.

The 60-Second Interview Pitch

Say this out loud before you type a single line

I'd solve this with Flattened Matrix Search: a flat index. Every row starts after the previous row ends, so reading the grid row by row gives one sorted list of m times n values, and I run a normal binary search over positions zero to m times n minus one without copying anything. For each mid I find the cell with divmod of mid by n: mid over n full rows come before it, and mid mod n is where it sits in its row. Then it's the usual three-way compare: return true on a match, otherwise move lo past mid or hi below it. The trap I avoid is dividing by m, the number of rows: a square test hides it, but on a three by four grid it reads the wrong cell. That's O(log(m times n)) time and O(1) space.

So: name the flat index, divide by the number of columns, and run Classic Binary Search unchanged.

Big-O Invariant Derivation

Complexity & Mathematical Proof

TIME COMPLEXITY

O(log(M * N))

SPACE COMPLEXITY

O(1)

The code keeps m, n, lo, hi, mid, row, col and val, whatever the matrix size, and returns one boolean. It never builds the flat list, so the extra space is O(1).

Formal Recurrence Relation

T(M·N) = T(M·N / 2) + O(1) = O(log(M * N))

Derivation Progression

Setup

O(1)

m, n = len(matrix), len(matrix[0]) and lo, hi = 0, m * n - 1 are constant work.

Halving loop

at most floor(log2(M·N)) + 1 passes

Each pass of while lo <= hi removes mid and one half of [lo, hi].

One probe

O(1) per pass

divmod(mid, n), one read matrix[row][col] and one comparison, whatever M and N are.

Total

O(log(M * N))

Constant work times a logarithmic number of passes.

Variable Definitions

$M$

Number of rows, len(matrix)

$N$

Number of columns, len(matrix[0])

$mid$

The flat index being probed, a position in the row-by-row list

Memory Architecture & Bounds

🟣 Call Stack

O(1) Iterative, no recursion

🔵 Auxiliary Heap

O(1): m, n, lo, hi, mid, row, col, val; no flattened copy

🟢 Output Space

O(1): one boolean

Boundary Best / Worst Cases

Best Case

$O(1)$ : target is at the first mid

Average Case

$O(\log(M \cdot N))$

Worst Case

$O(\log(M \cdot N))$ : target is absent or found on the last probe

Pointer Invariant Transition Progression

Synthesizing vector architecture diagram...

Staff+ Engineering Perspective

Senior SWE Deconstruction & Hardware Caveats

ARCHITECTURAL SIGNALS & INTERVIEW TRIGGERS

CONSTRAINTS & BOUNDS

FAANG PRODUCTION TRAPS & EDGE CASES

Core Algorithmic State Invariants

1. One Sorted List

Each row is sorted and starts after the previous row ends, so `matrix` read row by row is one sorted list of `m * n` values. Classic Binary Search needs nothing more.

2. Flat Index to Cell

Position `mid` has `mid // n` full rows before it and is `mid % n` cells into its row: `row, col = divmod(mid, n)`. The divisor is the row length `n`, never the row count `m`.

3. Closed Range, Logarithmic Probes

`[lo, hi]` starts at `[0, m * n - 1]` and every comparison drops `mid` and one half: at most about log2(m * n) + 1 probes, O(1) space, and the matrix is never copied.

Rosetta Dual-Monaco Comparison

Python 3

CANONICAL INVARIANT TEMPLATE

CONCRETE: SEARCH A 2D MATRIX (LEETCODE 74)

T = O(log(M * N))S = O(1)

Pattern Implementation Mapping TableCanonical Invariant ⟷ Concrete Code ⟷ Engineering Rationale

Canonical Invariant	Concrete Code	Engineering Rationale
lo, hi = 0, len(nums) - 1	`lo, hi = 0, m * n - 1`	The sorted list is every cell in reading order, so the closed range covers flat indices 0 to m * n - 1.
mid = lo + (hi - lo) // 2	`mid = lo + (hi - lo) // 2`	Unchanged from Classic Binary Search: the middle of the flat range.
nums[mid]	`row, col = divmod(mid, n) val = matrix[row][col]`	Each row holds n cells, so mid // n full rows come before position mid and mid % n is its place in the row. Divide by n, never by m.
if nums[mid] == target: return mid	`if val == target: return True`	A match ends the search at once; this problem only asks whether target is present.
elif nums[mid] < target: lo = mid + 1	`elif val < target: lo = mid + 1`	val is too small, and so is every earlier position: drop mid and everything before it.
else: hi = mid - 1	`else: hi = mid - 1`	val is too big, and so is every later position: drop mid and everything after it.
return -1	`return False`	An empty range means no cell can hold target.

Step

[lo, hi]

mid

row, col = divmod(mid, 4)

val

Compare with 3

Action

[0, 11]

(1, 1)

11 > 3

hi = mid - 1 = 4

[0, 4]

(0, 2)

5 > 3

hi = mid - 1 = 1

[0, 1]

(0, 0)

1 < 3

lo = mid + 1 = 1

[1, 1]

(0, 1)

3 == 3

Return True

m, n = len(matrix), len(matrix[0]) lo, hi = 0, m * n - 1 # every cell, as one sorted list while lo <= hi: mid = lo + (hi - lo) // 2 row, col = divmod(mid, n) # mid // n full rows come first; mid % n is the place in the row val = matrix[row][col] ...

Step

[lo, hi]

mid

row, col = divmod(mid, 4)

val

Compare with 3

Action

[0, 11]

(1, 1)

11 > 3

hi = mid - 1 = 4

[0, 4]

(0, 2)

5 > 3

hi = mid - 1 = 1

[0, 1]

(0, 0)

1 < 3

lo = mid + 1 = 1

[1, 1]

(0, 1)

3 == 3

Return True

Canonical Invariant

Concrete Code

Engineering Rationale

lo, hi = 0, len(nums) - 1

lo, hi = 0, m * n - 1

The sorted list is every cell in reading order, so the closed range covers flat indices 0 to m * n - 1.

mid = lo + (hi - lo) // 2

mid = lo + (hi - lo) // 2

Unchanged from Classic Binary Search: the middle of the flat range.

nums[mid]

row, col = divmod(mid, n)
val = matrix[row][col]

Each row holds n cells, so mid // n full rows come before position mid and mid % n is its place in the row. Divide by n, never by m.

if nums[mid] == target: return mid

if val == target:
    return True

A match ends the search at once; this problem only asks whether target is present.

elif nums[mid] < target: lo = mid + 1

elif val < target:
    lo = mid + 1

val is too small, and so is every earlier position: drop mid and everything before it.

else: hi = mid - 1

else:
    hi = mid - 1

val is too big, and so is every later position: drop mid and everything after it.

return -1

return False

An empty range means no cell can hold target.