Ordered Arrays

What Is an Ordered Array?

An ordered array is an array whose elements are kept in nondecreasing or nonincreasing order according to a comparison rule (e.g., numeric ascending, lexicographic, or a custom comparator). The array uses contiguous memory, which yields fast random access by index and good cache locality.

• Order invariant: After each update, the array remains sorted according to a comparator.
• Contiguous layout: Provides O(1) indexed access and predictable iteration.
• Comparator-driven: Elements can be ordered by built-in operators or custom comparison logic.

Why Use Ordered Arrays?

• Fast search: Binary search achieves O(log n) lookups.
• Cache-friendly: Sequential memory improves iteration and merge performance.
• Simple min/max: Extremes are at the ends (O(1)).
• Drawbacks: Insertions and deletions are O(n) due to shifting; resizing can be costly.

Core Operations and Typical Complexities

• Access by index: O(1)
• Search (membership, position): O(log n) via binary search
• Insertion (keep order): O(n) for shifting, after O(log n) position find
• Deletion: O(n) for shifting
• Merging two ordered arrays: O(n + m)
• Range queries (e.g., values in [a, b]): O(log n) to find bounds + O(k) to iterate k matches

Binary Search

Binary search uses divide-and-conquer over the index range to find a value or insertion point.

# Python: return index of x or -1 if not found
from typing import List

def binary_search(a: List[int], x: int) -> int:
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == x:
            return mid
        if a[mid] < x:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

Insertion While Preserving Order

Find the insertion point (with binary search), then shift elements to make space.

# Python using bisect for insertion point
import bisect

def insert_sorted(a, x):
    i = bisect.bisect_left(a, x)  # first position where x can go
    a.insert(i, x)                # O(n) shift; keeps order
    return i

Merging Two Ordered Arrays

The merge procedure walks both arrays linearly to produce a sorted result in O(n + m).

def merge(a, b):
    i = j = 0
    out = []
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            out.append(a[i]); i += 1
        else:
            out.append(b[j]); j += 1
    # append any remainder
    out.extend(a[i:])
    out.extend(b[j:])
    return out

Duplicates, Stability, and Comparators

• Duplicates: With a non-strict order (≤), duplicates cluster; choose lower_bound or upper_bound policies for insertion and search.
• Stability: The array is “stable” if equal elements retain relative order; merges typically preserve stability.
• Comparators: Must define a consistent strict weak ordering; avoid contradictory or non-transitive rules that can break invariants.

Range Queries and Bound Searches

Common patterns use two binary searches:

• lower_bound(x): First index i where a[i] ≥ x
• upper_bound(x): First index j where a[j] > x

The elements in [x, y] then lie in indices [lower_bound(x), upper_bound(y)).

Language and Library Tips

• Python: bisect.bisect_left/right for bounds; lists are dynamic arrays.
• C++: std::vector with std::lower_bound/upper_bound; merge via std::merge; custom comparators via functors/lambdas.
• Java: Arrays.binarySearch for arrays; Collections.binarySearch for lists; maintain sorted order manually on updates.
• JavaScript: Maintain order via custom comparator and binary search helpers; no built-in binary search—implement your own.

When to Choose Ordered Arrays

• Great for: Read-heavy workloads, frequent searches and scans, merging pre-sorted data, maintaining sorted logs or leaderboards with infrequent updates.
• Consider alternatives: Balanced trees (O(log n) insert/delete/search), hash tables (expected O(1) insert/search, but no order), heaps (fast extremes but not general search).

Performance Notes

• Cache locality: Beneficial for scans, merges, and even binary search.
• Batching updates: Buffer inserts, then sort or merge to amortize costs.
• Monotonic sequences: Specialized two-pointer methods can solve problems in linear time on ordered arrays.

Practice Ideas

• Implement binary search variants: first equal, last equal, lower_bound, upper_bound.
• Write a function that inserts a value while preserving order and deduplicates.
• Merge k ordered arrays efficiently.
• Answer range count queries using only bound searches.

Next Topic