6 Arrays and Collections Free Online FlashCards

What is an array?

An array is an ordered collection whose elements are stored under one variable name and accessed by index.

What indexes are valid for an array of length $n$?

For an array of length $n$, valid indexes range from $0$ through $n-1$.

What does updating an array element change?

Assigning a new value to one index changes that element but does not change the array's length.

What is array traversal?

Traversal visits each element, usually in order. A traversal of $n$ elements takes approximately $O(n)$ time.

What does linear search return when a target is absent?

Linear search checks elements from left to right and returns the first matching index, or $-1$ when the target is absent.

What prerequisite does binary search have?

Binary search requires the array to be sorted according to the same ordering used by the search.

How can an algorithm find every matching index?

Continue through the entire array and append every matching index. For [4, 2, 4, 7, 4], the matching indexes for 4 are [0, 2, 4].

What must an average algorithm decide for an empty array?

An average divides the sum by the number of elements, so the empty-array case must be handled before division.

How should an array maximum be initialized?

Initialize the candidate maximum from the first element, then compare the remaining elements with it.

How does an in-place array reversal work?

An in-place reversal swaps elements from both ends while moving inward. It runs in $O(n)$ time and uses $O(1)$ extra space.

How can a set improve duplicate detection?

A set records values already seen, allowing duplicate detection in approximately $O(n)$ time at the cost of additional memory.

Why sort an array before repeated searches?

Sorting rearranges values into an order, such as ascending order, which can enable binary search and simplify reporting.