AlgoScope

Array

Numbered slots side by side. Reading slot k is instant, but making room in the middle means shifting everything after it.

The player

Searching an unsorted array of 6 values for 2, one slot at a time.501142238435

Find 2. Nothing is sorted, so the only option is to check every slot in turn.

Check your understanding

The player pauses before each decision in this run and asks what happens next. Here are all 4, with their answers.

  1. Index 0 holds 5. Is that 2?

    • Match
    • Keep going

    Answer: Keep going. 5 is not 2, so the next slot is checked.

  2. Index 1 holds 1. Is that 2?

    • Match
    • Keep going

    Answer: Keep going. 1 is not 2, so the next slot is checked.

  3. Index 2 holds 4. Is that 2?

    • Match
    • Keep going

    Answer: Keep going. 4 is not 2, so the next slot is checked.

  4. Index 3 holds 2. Is that 2?

    • Match
    • Keep going

    Answer: Match. It matches, so the search stops here.

How it runs, step by step

  1. Find 2. Nothing is sorted, so the only option is to check every slot in turn.

    Searching an unsorted array of 6 values for 2, one slot at a time.

  2. Index 0 holds 5, not 2. Move on.

    Index 0 holds 5. That does not match.

  3. Index 1 holds 1, not 2. Move on.

    Index 1 holds 1. That does not match.

  4. Index 2 holds 4, not 2. Move on.

    Index 2 holds 4. That does not match.

  5. Index 3 holds 2. Found it after 4 checks.

    Index 3 holds 2. That matches.

  6. 2 is at index 3 after 4 checks. A different position would have cost a different number.

    2 was found at index 3.

The code

Array, in Python

def insert_at(a, size, index, value):
    for i in range(size - 1, index - 1, -1):
        a[i + 1] = a[i]   # shift right
    a[index] = value

def delete_at(a, size, index):
    for i in range(index + 1, size):
        a[i - 1] = a[i]    # shift left
    a[size - 1] = None

Array, in JavaScript

function insertAt(a, size, index, value) {
  for (let i = size - 1; i >= index; i--) a[i + 1] = a[i];   // shift right
  a[index] = value;
}

function deleteAt(a, size, index) {
  for (let i = index + 1; i < size; i++) a[i - 1] = a[i];    // shift left
  a[size - 1] = null;
}

Array, in Kotlin

fun insertAt(a: Array<Int?>, size: Int, index: Int, value: Int) {
    for (i in size - 1 downTo index) a[i + 1] = a[i]   // shift right
    a[index] = value
}

fun deleteAt(a: Array<Int?>, size: Int, index: Int) {
    for (i in index + 1 until size) a[i - 1] = a[i]    // shift left
    a[size - 1] = null
}

Write it yourself

Define linearSearch(values, target) and return the index of the target, or -1 when it is not there. It runs in your browser against this lesson's own 2 examples.

// Nothing is sorted here, so there is nothing to halve: look at each value in turn.function linearSearch(values, target) { return -1;}
6 linesTab indents. Escape, then Tab, leaves the editor. Ctrl-Enter runs (Cmd-Enter on a Mac).

    Remember

    • Access by index is O(1), because the address is just start plus index times slot size.
    • Insert or delete in the middle is O(n) because of the shifting.
    • A fixed array cannot grow. That is the problem dynamic arrays solve.

    Where this is used

    NumPy ndarrayScientific computing

    A NumPy array is one contiguous block of memory plus a shape and a set of strides, so element (i, j) is a single address computation rather than a chase through objects. When the block is contiguous and the dtype already matches, that layout is what lets NumPy pass it straight to BLAS or to vector CPU instructions with no repacking. It is also why np.insert returns a new array instead of editing in place: there is nowhere to put the extra element without moving the tail.

    The file descriptor tableOperating systems

    Linux keeps every open file of a process in a per-process array, and a file descriptor is just the index into it, which is why read(3, ...) resolves the file with one lookup on the syscall path. It also explains two behaviours programmers notice: descriptors are small integers, and open always returns the lowest free one, because the kernel keeps a bitmap of which slots are taken and picks the first zero bit.

    Line pointers in a PostgreSQL pageDatabases

    An 8 KB heap page begins with a small header, and right after it sits an array of fixed-size line pointers, four bytes each. A row's CTID is the pair (page number, index into that array). The fixed size is the whole point: the database reaches slot k by arithmetic, with no scan of the page. A line pointer is never moved until it is freed, so when the page is compacted and the row itself slides to a different offset, the slot number an index entry already holds still finds it.

    Vertex buffers on the GPUGraphics

    A mesh is uploaded as one flat array of vertices with a declared stride, and an index buffer is a second array of integers naming which vertices to draw. Because the stride is fixed and declared up front, the hardware works out the address of vertex k without reading anything first, so thousands of cores fetch their own vertices in parallel with no coordination. A pointer-chasing layout would make every fetch wait on the load before it.

    Why it works this way

    Why do indexes start at zero?

    The address of slot k is start + k * slotSize, so with zero-based indexing the index is literally how far the slot sits from the start and the base address needs no correction term. It also keeps ranges clean: 0 <= i < n has no off-by-one at either end, the half-open range [i, j) has length exactly j - i, and an empty range is just i == j instead of a special case.

    Why can the shifting not be avoided?

    The O(1) lookup only works because slot k sits at a position computed from k alone. Inserting in the middle renumbers every element after the gap, and a renumbered element has to physically move to its new address, so the shift is the price of the lookup rather than a sloppy implementation. In this flat layout you cannot have both O(1) indexing and O(1) middle insert. Text editors dodge it with a gap buffer: they park the empty space at the cursor, so typing is cheap and only moving the cursor pays for a shift.

    Deleting while looping forward skips elements

    Writing for (i in 0 until size) { if (a[i] == x) deleteAt(a, size, i) } silently misses matches. After the shift, the element that was at i + 1 has moved into slot i, and the loop has already advanced past it, so two matches in a row only lose one. Iterate backwards, or do not advance i on a delete. Better still, sweep once with two pointers and copy the keepers forward, which removes everything in a single O(n) pass instead of one O(n) shift per removal.

    Clearing the vacated slot is not tidiness, it is a leak fix

    deleteAt writes null into the last slot after shifting. If you only decrement the size and leave the stale reference behind, the array is still holding a live pointer to an object the program has logically thrown away, and a garbage collector cannot free it. The array stays as large as it ever was, so the leak grows with the high-water mark, not the current contents. This is the classic bug in a hand-rolled stack or list class.

    Read more

    Next up