Skip to section
Foundationsfor rotation-free search
Section 2 of 524% of course
Contents
Chapter 1 Section 1.2 52 min

Part I · Mathematical foundations

Indices: names for positions

Read zero-based indices and translate between arrays and mathematical subscripts.

A reusable name for “the current position”

Writing out “position 0, then position 1, then position 2” gets tedious quickly. Instead, we introduce a variable—usually we just use i—that stands in for whichever position we happen to be discussing right now.

In code, we write a[i]. Mathematics usually writes ai. Both mean the exact same thing: “the value inside list a at position i.”

Plain languageCodeMathematics
value at position 0a[0]a0
value at position 3a[3]a3
value at the current positiona[i]ai

Worked example

Evaluate a subscript

Let's say a = [9, −4, 8, 2]. That means a0 = 9, a2 = 8, and a3 = 2. A subscript is not a multiplier. a2 doesn't mean "2 times a"; it's just naming a location.

Use a symbol for the length

Let's use D to represent the length of our list. Since positions begin at zero, the valid range of indices is:

0, 1, 2, …, D − 1
012…D−2D−1

The mathematical notation 0 ≤ i < D says exactly the same thing compactly: our index i can start at zero, and it has to stay strictly smaller than D.

Translate the range as a loop contract

That inequality has two halves. The 0 ≤ i part stops our loop from wandering off before the first entry. The i < D part stops it from taking one step too far past the last entry. Think of the whole statement as simply saying: “i is a valid position in a list of length D.”

D = len(a)
for i in range(D):
    use(a[i])

Python’s range(D) gives us 0, 1, …, D−1. The stopping value D is naturally excluded, matching perfectly with how the strict inequality works.

Worked example

Trace the smallest nonempty case

If our list has length D=1, the condition is 0 ≤ i < 1. Only i=0 satisfies this. The list has exactly one entry and its final index is zero. Testing this tiny edge case is a great way to catch yourself if you accidentally make D an upper bound.

Check your understanding

A list has length D = 128. What is its final valid index?

Two indices name a grid location

Sometimes data is arranged as a list of lists, like a matrix or a 2D array. In that case, vj,i usually means “entry i inside list j.” We read from the outside inward: choose list j first, then pick position i within it.

i=0i=1i=2i=3j=04192j=13805

Looking at that grid, v1,2 = 0. We went to row j=1, and looked at position i=2. The comma just separates two independent position choices.

Check your understanding

In the displayed grid, what is v₀,₃?

Keep the two jobs visually distinct

When you see several indices in a formula, it helps to write down the role of each one before you start calculating. In the grid above, j selects a list and i selects a position inside that list. Later on, we might use two indices to independently pick one term from each of two different lists. The letters can be anything; the important thing is that their roles don't silently change halfway through your work.

Debug this loop: for i in range(D + 1)

It visits D+1 positions: 0 through D. Since a length-D list ends at D−1, that final lookup will throw an out-of-bounds error. We should just use range(D).

Check your understanding

Which condition guarantees that i is a valid index of a length-D list?

Section summary

  • An index is just a fancy word for a position.
  • a[i] and ai are just different ways to write the exact same lookup.
  • A list of length D uses indices 0 through D−1.
  • Two subscripts can be used together to locate an entry in a 2D grid.

Repository layer · second pass

How do subscripts let one statement talk about every position?

A subscript is an address written beside a symbol. In aᵢ, the letter a names the whole list and i names one position. When i is allowed to vary, a single expression describes a family of concrete reads: a₀, a₁, a₂, and so on. This is mathematical parameterization, much like a function argument in code.

With a collection of vectors, two indices answer two different questions. In vⱼ,ᵢ, j selects a vector from the corpus and i selects a coordinate inside that vector. Keeping those roles distinct prevents one of the most common derivation errors in this course.

Reasoning chain

  1. 1

    Name the container first.

  2. 2

    Choose one symbol for the outer item and another for the inner position.

  3. 3

    Write the valid range for each index.

  4. 4

    Substitute concrete values before manipulating an unfamiliar formula.

Worked trace

Read a two-index table without guessing

  1. Let v₀ = [2, 8, 1] and v₁ = [5, 0, 4].
  2. In v₁,₂, the first index selects v₁.
  3. The second index selects position 2 inside [5, 0, 4].
  4. That stored value is 4.

Result. v₁,₂ = 4; reversing the two indices would ask a different question.

Executable lens · Python

Make the hidden state visible

vectors = [[2, 8, 1], [5, 0, 4]]
j = 1  # which vector?
i = 2  # which coordinate?
assert vectors[j][i] == 4

Retype this example, predict each intermediate value, and then change one input that touches a boundary.

Misconception clinic

Tempting mistakes

  • Treating i and j as decoration instead of variables with declared ranges.
  • Silently switching between one-based prose and zero-based formulas.

Retrieval and transfer

Close the book first

  1. Write every valid pair (j, i) for two vectors of length three.
  2. Translate corpus[3][17] into subscript notation.
  3. State the final valid i when D = 768.