Chapter 2: Working with Data

Every useful program must handle data. Whether it is processing numbers, searching for text, or organizing information into lists, the ability to manage and manipulate data efficiently lies at the heart of algorithms. In this chapter, you will learn how algorithms work with collections of dat; how they search for information, how they sort it into order, and how to evaluate their efficiency using performance analysis. Finally, you will apply these concepts to a practical example: managing a contact list through simple algorithms written in Python.

Data comes in many forms: numbers, strings, records, and objects. But regardless of type, the operations you perform on it tend to fall into common categories such as searching, sorting, inserting, deleting, and analyzing. The better you understand these operations and their performance characteristics, the better your algorithms will be.

Searching for Information

Searching is one of the most fundamental algorithmic tasks. Whenever you look for an item in a list, a record in a database, or a keyword in a document, you are performing a search. The way you choose to search depends on how your data is organized.

The simplest form of searching is the linear search (also known as sequential search). It works by examining each element in a list one by one until the desired value is found or the list ends. Although easy to implement, this approach becomes inefficient for large datasets because it must check every element in the worst case.

numbers = [8, 2, 7, 4, 9, 1]
target = 4

for n in numbers:
  if n == target:
    print("Found!")
    break

This algorithm performs well on small lists but scales poorly. If there are n elements, it may require checking all n to find a match.

A faster approach is the binary search, which works only on sorted data. It begins by checking the middle element; if that element is too high or too low, it discards half of the remaining list and repeats. Each step cuts the search space in half, leading to dramatically faster performance for large datasets.

numbers = [1, 2, 4, 7, 8, 9]
target = 4

low = 0
high = len(numbers) - 1

while low <= high:
  mid = (low + high) // 2
  if numbers[mid] == target:
    print("Found!")
    break
  elif numbers[mid] < target:
    low = mid + 1
  else:
    high = mid - 1

Because each step eliminates half of the remaining possibilities, binary search grows much more slowly with data size. For a list of one million items, it only takes around twenty steps to find the target, or to confirm it is not present.

Sorting Data Efficiently

Sorting is another core operation in algorithmic work. Ordered data not only improves readability but also makes searching and analysis more efficient. Many algorithms rely on sorted input to perform effectively.

The simplest way to sort a list is with a bubble sort. Although rarely used in professional code due to its slowness, it is easy to understand and serves as an introduction to sorting logic.

numbers = [5, 2, 8, 1, 4]

for i in range(len(numbers) - 1):
  for j in range(len(numbers) - i - 1):
    if numbers[j] > numbers[j + 1]:
      numbers[j], numbers[j + 1] = numbers[j + 1], numbers[j]

In each pass, the largest unsorted value “bubbles up” to its correct position. Although simple, this method performs slowly because it repeatedly traverses the list, making roughly n² comparisons.

A more efficient approach is merge sort, which divides a list into halves, sorts each half, and then merges them together. This divide-and-conquer approach reduces comparisons and handles large datasets efficiently.

        ┌────────────────────┐
        │ [8, 3, 2, 9, 5, 1] │
        └─────┬──────────────┘
              │
       Split into halves
        ┌─────┴─────┐
        │ [8, 3, 2] │ [9, 5, 1]
        └─────┬─────┘
              │
       Recursively sort and merge

Each level of division and merging processes fewer and fewer comparisons, leading to an average complexity of O(n log n). Merge sort’s efficiency and predictability make it a foundation of many built-in sorting functions.

Analyzing Performance and Big-O Notation

Not all algorithms are created equal. Two pieces of code may produce the same result but differ greatly in how long they take or how much memory they use. To compare them objectively, computer scientists use a mathematical model called Big-O notation to describe how an algorithm’s performance scales with input size.

Big-O focuses on the growth rate of an algorithm’s operations rather than specific timing. It ignores constant factors and measures how quickly execution time increases as data grows. The table below shows some common complexities:

When analyzing algorithms, the goal is not to measure how fast a program runs on your computer, but to understand how its efficiency changes as the dataset grows. This understanding allows you to predict performance and choose the best algorithm for a given problem.

Time vs. Space Trade-Offs

Efficiency is not just about speed. Some algorithms use more memory to run faster, while others conserve memory but take longer to complete. This relationship between runtime and memory usage is known as the time–space trade-off.

For example, a simple linear search requires almost no extra memory (it only stores the list and one variable for comparison) but it takes longer to find items. A binary search, by contrast, needs the list to be sorted, which can require extra memory or preprocessing time.

Another example comes from caching: storing computed results so they can be reused instead of recalculated. This technique, known as memoization, increases memory use but speeds up computation significantly when results are repeated.

When designing algorithms, consider the environment they will run in. Embedded systems, for example, may prioritize minimal memory use, while high-performance computing may emphasize speed over memory. Understanding this balance helps you select the right data structures and algorithmic strategies for each scenario.

Practical Case Study: Managing a Contact List

To tie these concepts together, let’s apply them to a realistic example: managing a simple contact list. Suppose you are building a small address book that allows adding, searching, and sorting names.

We can represent the contacts as a list of strings and apply the algorithms learned so far:

contacts = ["Alice", "Bob", "Charlie", "Diana", "Eve"]

# Searching for a name
target = "Charlie"
for name in contacts:
  if name == target:
    print("Contact found:", name)

# Sorting the contacts alphabetically
contacts.sort()
print("Sorted contacts:", contacts)

This program uses a linear search for simplicity and Python’s built-in sort() method, which implements the highly optimized Timsort algorithm (a hybrid of merge sort and insertion sort). The result is an efficient, real-world sorting method that performs well even on large lists.

If we wanted to improve search performance, we could first ensure the list is sorted, then apply a binary search algorithm instead of a linear one. This small change can make a significant difference for larger datasets.

In larger applications, contact lists might be stored in databases, where indexes and optimized query algorithms replace manual search and sort operations. Yet the same principles still apply: efficient data handling always depends on the underlying algorithms.

This chapter has shown how algorithms transform data into useful information, focusing on searching, sorting, and analyzing efficiency. In the next chapter, we will build on these ideas by examining how data can be organized and manipulated using structures such as stacks, queues, and linked lists.