Data Structures: Linear Lists, Contiguous Arrays, and Traversal Algorithms
In Senior Secondary 1, you learned how to store individual variables in Python: integers, strings, and floats. But modern software engineering requires managing thousands or millions of related records—such as 100,000 student WAEC scores or banking transactions across Nigeria.
Storing millions of items in separate variable names (score1, score2, score3) is impossible. Instead, computer science organizes data using Data Structures.
In this lesson, we study Contiguous Arrays, calculate how CPUs locate data in physical RAM, compare Linear Search with Binary Search, and introduce Big-O Performance Notation.
Learning Outcomes
By the end of this lesson, you will be able to:
- Distinguish between Contiguous Arrays and Dynamic Lists in hardware memory.
- Calculate exact physical memory addresses using the Base Address formula.
- Implement Linear Search ($O(N)$) and Binary Search ($O(\log N)$).
- Evaluate computational efficiency using Big-O time complexity notation.
Key Vocabulary
| Term | Technical Definition |
|---|---|
| Data Structure | A specialized format for organizing, processing, retrieving, and storing data efficiently in memory. |
| Array | A contiguous collection of elements of the same data type stored at sequential memory addresses. |
| Base Address | The physical memory address of the very first element (index $0$) of an array. |
| Time Complexity | A mathematical description of how an algorithm's execution time scales as the input dataset size ($N$) grows. |
| Big-O Notation | Standard notation representing the worst-case asymptotic upper bound of algorithm runtime (e.g., $O(1), O(N), O(\log N)$). |
| Binary Search | An efficient search algorithm that repeatedly divides a sorted dataset in half until the target is found. |
The Contiguous Array: Physical Memory Layout
In computer memory (RAM), a standard array is allocated as an unbroken, contiguous block of bytes.
Suppose we declare an array of 5 integers: scores = [78, 92, 85, 64, 99]. Each integer takes 4 bytes in memory. The operating system allocates 20 contiguous bytes starting at Base Address 0x4000 (decimal 16,384):
Index: [0] [1] [2] [3] [4]
Value: 78 92 85 64 99
Byte Address: 16384-16387 16388-16391 16392-16395 16396-16399 16400-16403
The Array Address Calculation Formula
To access element at index $i$:
$$\text{Address}(A[i]) = \text{Base} + (i \times S)$$
Where: - $\text{Base}$ is the starting memory address. - $i$ is the target index ($0$-based). - $S$ is the size of each data element in bytes.
Because this calculation requires only one multiplication and one addition, the CPU can read any index instantly ($O(1)$ constant time), whether the array has 10 items or 10 million items!
Searching Algorithms: Linear vs Binary Search
When we need to find an item in an array, how we search makes a massive difference to system speed.
1. Linear Search ($O(N)$ Linear Time)
The algorithm inspects elements sequentially from beginning to end until the target is found. - Advantage: Works on any list, whether sorted or unsorted. - Disadvantage: If the target is at the very end (or not present), the algorithm must check all $N$ elements. For 1,000,000 items, it takes up to 1,000,000 comparisons.
2. Binary Search ($O(\log N)$ Logarithmic Time)
The algorithm requires the dataset to be sorted. It compares the target with the middle element: - If target equals middle, search succeeds. - If target is smaller than middle, search continues in the left half. - If target is larger than middle, search continues in the right half.
Searching for 85 in sorted array: [12, 24, 38, 55, 67, 85, 92, 99]
Step 1: Check middle (55). 85 > 55. Discard left half!
Remaining: [67, 85, 92, 99]
Step 2: Check middle (85 or 92). Target 85 FOUND in only 2 comparisons!
Practical Activity: Comparing Linear and Binary Search in Python
Let us implement both search algorithms and measure the number of comparisons each requires on a dataset of 1,000 student IDs.
Step 1: Create search_benchmark.py
# Linear Search with comparison counter
def linear_search(data_list, target):
comparisons = 0
for idx, value in enumerate(data_list):
comparisons += 1
if value == target:
return idx, comparisons
return -1, comparisons
# Binary Search with comparison counter
def binary_search(sorted_list, target):
comparisons = 0
low = 0
high = len(sorted_list) - 1
while low <= high:
comparisons += 1
mid = (low + high) // 2
mid_val = sorted_list[mid]
if mid_val == target:
return mid, comparisons
elif target < mid_val:
high = mid - 1
else:
low = mid + 1
return -1, comparisons
# Generate a sorted list of 1,000 student IDs
dataset = [1000 + i for i in range(1000)]
target_id = 1999 # Worst-case target at the very end of list
lin_idx, lin_steps = linear_search(dataset, target_id)
bin_idx, bin_steps = binary_search(dataset, target_id)
print("=== Search Performance Comparison (N = 1,000 items) ===")
print(f"Target ID: {target_id}")
print(f"Linear Search: Found at index {lin_idx} in {lin_steps} comparisons")
print(f"Binary Search: Found at index {bin_idx} in {bin_steps} comparisons")
print(f"Efficiency Ratio: Binary Search was {lin_steps // bin_steps}x more efficient!")
Step 2: Run the Benchmark
Execute the Python script in your terminal:
Expected Results and Model Output
When you run search_benchmark.py, you will see:
=== Search Performance Comparison (N = 1,000 items) ===
Target ID: 1999
Linear Search: Found at index 999 in 1000 comparisons
Binary Search: Found at index 999 in 10 comparisons
Efficiency Ratio: Binary Search was 100x more efficient!
Key Takeaway: For $N = 1,000$, Linear Search required 1,000 steps, while Binary Search found the target in just 10 steps! If $N$ were $1,000,000$, Linear Search would take up to $1,000,000$ steps, while Binary Search would take only $20$ steps.
Common Mistakes to Avoid
- Attempting Binary Search on Unsorted Data: If the array is not sorted, Binary Search will discard regions where the target actually resides, returning false negatives.
- Off-by-One Array Indexing Errors: Remembering that arrays in most modern programming languages (Python, C, Java) are zero-indexed: the first item is
arr[0], and the last item in a list of length $N$ isarr[N-1]. - Assuming Python Lists Are Static Arrays: In Python, lists are dynamic arrays of references. When you append elements, Python automatically reallocates contiguous memory blocks behind the scenes.
Notebook Summary
- Arrays store elements at contiguous memory locations, allowing instant $O(1)$ random access using the address formula: $\text{Base} + (i \times S)$.
- Linear Search ($O(N)$) checks every item sequentially; it works on any list but is slow for large datasets.
- Binary Search ($O(\log N)$) requires sorted data; it divides the search space in half on each step, finding targets in huge datasets in dozens of comparisons.
- Big-O Notation categorizes algorithmic efficiency as input scale approaches infinity.
Optional Extension Challenge
Write a Python function two_dimensional_address(base, rows, cols, r, c, element_size) that calculates the physical memory address of an element at row r and column c in a 2D array stored in Row-Major Order:
$$\text{Address}(A[r][c]) = \text{Base} + ((r \times \text{cols} + c) \times \text{element_size})$$
Verify the formula with a $4 \times 5$ matrix.