CQH103: Searching Algorithms – Binary Search vs. Linear Search

Finding information quickly is one of the most important things a program can do. Whether you’re looking up a username, checking if a number is in a list, or navigating a game map, you’re performing a search.

In this post, we’ll dive into two fundamental searching algorithms: Linear Search and Binary Search. Each has its strengths, and understanding how they work—and how they interact with data structures—is key to writing efficient code.

Linear Search – Simple but Slow

Linear search is the most straightforward way to find something in a collection: just look at every element, one at a time.

How It Works

  1. Start at the beginning of the list.
  2. Check each element until you find a match (or reach the end).

Python Example

def linear_search(data, target):
    for i in range(len(data)):
        if data[i] == target:
            return i  # Return the index
    return -1  # Not found

nums = [4, 2, 7, 1, 9]
print(linear_search(nums, 7))  # Output: 2

Performance

  • Time Complexity: O(n)
  • Best For: Small or unsorted datasets

Use Cases

  • Searching in an unsorted array or list.
  • One-time searches where setup time isn’t worth it.

Binary Search – Fast but Requires Sorted Data

Binary search is like playing a game of “guess the number” with half the range eliminated on every guess.

How It Works

  1. Start with the middle element.
  2. If the target is less, search the left half.
  3. If it’s greater, search the right half.
  4. Repeat until you find the element or the range is empty.

Python Example

def binary_search(data, target):
    low = 0
    high = len(data) - 1

    while low <= high:
        mid = (low + high) // 2
        if data[mid] == target:
            return mid
        elif data[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

nums = [1, 2, 4, 7, 9]
print(binary_search(nums, 7))  # Output: 3

Performance

  • Time Complexity: O(log n)
  • Best For: Large datasets that are already sorted

Use Cases

  • Searching in sorted arrays or binary search trees
  • Efficient querying in large, static datasets

Data Structures and Search Performance

Algorithms don’t live in isolation—they rely on how data is stored.

Data Structure Supports Linear Search Supports Binary Search Notes
Array ✅ ✅ (if sorted) Random access enables binary search
Linked List ✅ 🚫 No random access, linear only
Binary Search Tree ✅ ✅ Structure supports binary search without needing sorting
Hash Table 🚫 (uses hashing) 🚫 Uses hashing for constant-time lookups (different technique)

When you use a searching algorithm, you’re really implementing a behavior over a data structure. For example:

  • An array gives you index access—perfect for binary search.
  • A linked list must be searched linearly.
  • A tree can be traversed in a way that mimics binary search.

Choosing the right combination of data structure + algorithm is key to solving problems efficiently.

Challenge Time! 🔍

  • Implement both linear_search and binary_search for a list of 100 numbers.
  • Measure the number of comparisons each makes for a number in the middle.
  • Bonus: What happens when the number isn’t in the list at all?

Can you build a timer function to measure which is faster? Post your findings and code in the comments!

Next up: We’ll tackle Graph Algorithms with Dijkstra’s Algorithm, where finding the shortest path becomes a bit more… adventurous. 🗺️