Arrays, Dynamic Arrays and Searching

1. Array Representation

An array stores a fixed number of same-type element slots indexed by consecutive integers. Conceptually, elements occupy contiguous positions:

index:  0   1   2   3
value: 18   7  24  11

In Java, an array object has a fixed length established at creation. An array variable stores a reference to that object. For object arrays, slots contain references and initially hold null. Primitive arrays contain primitive values initialized to their type defaults.

int[] values = new int[10];
String[] names = new String[5];

2. Constant-Time Indexing

An array representation can locate element i from a base location and a fixed element-slot scale. In the usual RAM model, indexed access and replacement are O(1):

int x = values[i];
values[i] = 42;

This assumes a valid index. Java checks bounds and throws ArrayIndexOutOfBoundsException when i is negative or at least length.

Constant-time access does not mean retrieving an element by its value is constant. Without another index or ordering, finding a value still requires search.

3. Traversal

Visiting every n elements takes Θ(n):

for (int value : values) {
    process(value);
}

Arrays offer strong spatial locality because consecutive slots are stored close together. Sequential traversal can therefore be efficient in practice as well as linear asymptotically.

Traversal should use the logical size when an array is serving as backing storage for a partially filled structure. Capacity slots beyond size do not represent stored elements.

4. Insertion and Deletion

Inserting into a packed array at index i requires shifting elements i through size - 1 one position right:

[A, B, C, D, _]
insert X at 1
[A, X, B, C, D]

Worst-case time is Θ(n). Deleting from the middle similarly shifts later elements left.

Insertion at the logical end is Θ(1) when an unused slot exists. Removing the last element is also Θ(1). Ordering requirements create the shift cost.

If order does not matter, deletion can copy the final element into the removed position and reduce size in O(1), though this changes element order.

5. Size and Capacity

Size is the number of logical elements. Capacity is the number of slots allocated in the backing array.

The representation invariant for a simple dynamic array is:

0 <= size <= elements.length
logical elements occupy elements[0 .. size-1]

Unused object-reference slots should be cleared after deletion so removed objects can be garbage-collected.

Capacity is an implementation detail. Clients should not treat unused slots as part of the collection.

6. Dynamic Arrays

A dynamic array grows when its backing array becomes full:

allocate a larger array;
copy the existing size elements;
replace the backing reference;
insert the new element.

Java ArrayList implements a dynamic-array abstraction, though exact growth policy is an implementation detail rather than an application contract.

Indexed access remains O(1), middle insertion remains O(n) and append is O(1) amortized.

7. Geometric Growth

Growing capacity by a multiplicative factor such as two keeps append amortized constant. Across n appends, the number of copied elements is bounded by a geometric series:

1 + 2 + 4 + ... < 2n

Total copying is O(n) and the n ordinary writes add O(n), so average charged cost per append is O(1).

Growing by one slot each time would copy:

1 + 2 + ... + n = Θ(n²)

across n appends, producing Θ(n) amortized append cost.

8. Shrinking

Automatically shrinking on every deletion can cause repeated grow-shrink oscillation near a boundary.

A dynamic array can shrink only when size falls below a lower fraction of capacity, creating hysteresis. Many libraries avoid automatic shrinking and provide an explicit trim operation because reserved capacity can be valuable for future growth.

Shrinking invalidates assumptions about backing storage and costs Θ(n) to copy retained elements.

9. Linear Search

Linear search examines elements in sequence:

static int linearSearch(int[] a, int key) {
    for (int i = 0; i < a.length; i++) {
        if (a[i] == key) {
            return i;
        }
    }
    return -1;
}

It requires no sorted order. Best case is Θ(1) when the first element matches. Worst case is Θ(n) when the target is last or absent.

For one search over unsorted data, linear search can be better than sorting first.

10. Linear-Search Correctness

Before iteration i, the invariant is:

key does not occur in positions 0 through i - 1

It holds initially because that prefix is empty. If a[i] equals key, returning i is correct. Otherwise the failed comparison extends the known absent prefix.

If the loop terminates at i = n, every position has been checked, so -1 correctly reports absence.

This implementation returns the first matching index because it scans left to right and returns immediately.

11. Sentinel Search

A sentinel technique temporarily places the key at the end so the inner loop need not check both index and equality on every step. It then determines whether the match was original or sentinel.

This requires writable storage and careful restoration. On modern managed systems, the small branch reduction may not justify mutation and complexity.

It demonstrates a broader idea: extra structural guarantees can simplify a loop, but they must preserve the input contract.

12. Binary Search

Binary search works on data sorted under the same comparison used by the search. It compares the target with a midpoint and discards the half that cannot contain a match.

static int binarySearch(int[] a, int key) {
    int low = 0;
    int high = a.length - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;

        if (a[mid] == key) {
            return mid;
        } else if (a[mid] < key) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1;
}

13. Search-Interval Invariant

For inclusive bounds [low, high], the invariant is:

if key occurs in the array, a possible matching index lies in [low, high]

Initially the interval covers the whole array. If a[mid] < key, sorted order proves that positions through mid cannot match, so low becomes mid + 1. If a[mid] > key, positions from mid onward cannot match, so high becomes mid - 1.

Equality returns a valid match. If low exceeds high, the interval is empty and the target is absent.

14. Midpoint Calculation

The simple expression:

(low + high) / 2

can overflow when low and high are large positive integers.

Use:

low + (high - low) / 2

for valid bounds. The difference remains within the interval length.

Overflow-aware arithmetic is part of correctness even when ordinary tests use small arrays.

15. Termination

Every unsuccessful binary-search iteration removes the tested midpoint and strictly shrinks the candidate interval.

Using low = mid instead of mid + 1 can leave a one- or two-element interval unchanged and produce an infinite loop. Bound updates must match whether endpoints are inclusive or exclusive.

Since interval length is a nonnegative integer that decreases, the loop terminates. Repeated halving gives Θ(log n) comparisons.

16. Inclusive and Half-Open Forms

The implementation above uses inclusive [low, high]:

low = 0
high = n - 1
continue while low <= high

Another valid design uses half-open [low, high):

low = 0
high = n
continue while low < high

Its updates and result interpretation differ. Many off-by-one errors come from mixing invariants from the two forms. Choose one form and derive every condition from it.

17. Duplicates

Ordinary binary search may return any matching duplicate:

[2, 4, 4, 4, 9]

If the contract requires the first occurrence, retain a candidate on equality and continue left:

result = mid
high = mid - 1

For the last occurrence, continue right. A lower-bound search returns the first index whose value is not less than key. An upper-bound search returns the first index whose value is greater than key.

The range of equal keys is [lowerBound, upperBound).

18. Lower Bound

Half-open lower bound:

static int lowerBound(int[] a, int key) {
    int low = 0;
    int high = a.length;

    while (low < high) {
        int mid = low + (high - low) / 2;
        if (a[mid] < key) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return low;
}

Invariant:

indices below low contain values less than key;
indices at or above high contain values not less than key;
the unknown boundary lies in [low, high].

The returned index is also the correct insertion position that preserves ascending order.

19. Binary Search and Comparators

Searching objects requires an ordering:

int comparison = comparator.compare(a[mid], key);

The array must already be sorted by a comparator consistent with the search comparator. Sorting by employee name and searching with employee ID ordering invalidates the partition reasoning.

Comparison cost may not be O(1). Comparing long strings can inspect many characters, so total time can be O(log n) comparisons but more than O(log n) character work.

20. Searching a Linked List

Binary search relies on efficient midpoint access. An array reaches a[mid] in O(1), giving O(log n) total comparison steps and access time under the standard model.

A linked list needs linear traversal to reach a middle node. Repeated midpoint location removes the ordinary logarithmic total-time benefit.

Sorted linked structures use other techniques or augment nodes. A balanced search tree provides logarithmic navigation without contiguous indexing.

21. Search Versus Preprocessing

Sorting solely to perform one search costs O(n log n), more than one O(n) linear search.

For many searches over mostly static data, one sorting cost plus many O(log n) searches can be worthwhile. A hash table may provide expected O(1) lookup if ordering is unnecessary. A balanced tree supports ordered updates and range queries.

Count all operations over the data's lifetime, including updates and preprocessing.

22. Two-Dimensional Arrays

A Java rectangular two-dimensional array is an array of row references:

int[][] matrix = new int[rows][cols];

Access to a known matrix[i][j] is O(1), but visiting every element is Θ(rows × cols).

Java also permits jagged arrays with different row lengths. Algorithms must use matrix[i].length rather than assuming one universal column count.

23. Copying Arrays

Copying n element slots takes Θ(n):

int[] copy = Arrays.copyOf(original, original.length);

For object arrays, this is a shallow copy of references. The array objects are distinct, but referenced mutable elements remain shared.

Deep copy requires a defined way to copy each element and may have a cost based on the entire reachable content.

24. Boundary Cases

Search and dynamic-array tests should include:

empty input;
one element, present and absent;
first and last positions;
duplicate values;
all equal values;
values below minimum and above maximum;
full capacity followed by append;
insertion at zero and at size;
deletion from first, middle and last positions.

Check contracts for null arrays, null elements, invalid indices and comparator behavior.

25. Choosing an Array-Based Structure

Arrays are strong when indexed access, compact storage and traversal dominate. Dynamic arrays add growth while retaining locality.

They are weaker for frequent ordered insertion or deletion near the beginning because elements shift. Linked structures avoid shifting but add pointer overhead and lose constant-time indexing and cache locality.

Choose from the workload. Then prove index bounds and search invariants, state sorted-order requirements and distinguish logical size from allocated capacity.