Intermediate · 25 minYou are hereRead
Arrays of two and more dimensions
A grid, or a block of any number of dimensions, is stored as one line of cells, row after row in C. An index becomes an offset by multiplying each index by its stride.
Arrays and strings
Arrays
Lessons on this topic
Intermediate · 25 minYou are hereRead
Inserting and deleting in an array
An array kept with its length and capacity becomes a reusable structure. Inserting or deleting in the middle shifts everything after it, so the cost depends on where.
Intermediate · 20 minYou are hereRead
Linear search
An unsorted array can only be searched cell by cell. Moving found items to the front speeds up later searches when a few keys are asked for often.
Intermediate · 25 minYou are hereRead
Binary search
In a sorted array, comparing with the middle discards half of what is left, so at most ⌊log₂ n⌋ + 1 probes find a key or prove it absent.
Intermediate · 20 minYou are hereRead
Merging and set operations
Two sorted arrays merge into one in a single pass by always taking the smaller front item. The same walk, keeping different items, gives union, intersection and difference.
Intermediate · 25 minYou are hereRead
Dynamic arrays
An array that doubles its capacity when full copies fewer than 2n elements over n appends, so an append costs O(1) on average. Growing by a fixed amount costs O(n²) copies in all.
Related topics