Searching algorithms (linear, binary) in Intro to Computing - Full Explanation

Introduction

Finding a specific item in a list can be tricky if the list is long. Searching algorithms help us quickly locate what we want without checking every single item blindly.

Explanation

Linear Search

Linear search checks each item in the list one by one from the start until it finds the target or reaches the end. It works on any list, whether sorted or not, but can be slow for large lists because it might check every item.

Linear search looks through each item in order until it finds the target or finishes the list.

Binary Search

Binary search works only on sorted lists. It starts by looking at the middle item and compares it to the target. If the target is smaller, it repeats the search on the left half; if larger, on the right half. This splitting continues until the target is found or the search area is empty.

Binary search quickly narrows down the search by repeatedly dividing the sorted list in half.

Real World Analogy

Imagine looking for a word in a dictionary. You don't check every page from the start. Instead, you open near the middle, see if the word is before or after, then open halfway in that section, repeating until you find the word.

Linear Search → Flipping through every page of a book from start to finish to find a word.

Binary Search → Opening a dictionary near the middle and narrowing down the pages by halves to find a word quickly.

Diagram

Diagram

List: [2, 4, 6, 8, 10, 12, 14]

Linear Search:
Start → 2 → 4 → 6 → 8 → ... until target found

Binary Search:
Step 1: Check middle (8)
Step 2: Target < 8? Search left half [2,4,6]
Step 3: Check middle (4)
Step 4: Target > 4? Search right half [6]
Step 5: Check 6 → Found or not

This diagram shows how linear search checks items one by one, while binary search splits the list and checks the middle repeatedly.

Key Facts

Linear Search → A search method that checks each item in order until the target is found or the list ends.

Binary Search → A search method that repeatedly divides a sorted list in half to find the target quickly.

Sorted List → A list where items are arranged in order, such as numbers from smallest to largest.

Search Efficiency → Binary search is faster than linear search on large sorted lists because it skips half the items each step.

Common Confusions

Binary search can be used on any list.

Binary search can be used on any list. Binary search <strong>only works on sorted lists</strong>; using it on unsorted lists will not find the correct result.

Linear search is always slow.

Linear search is always slow. Linear search can be fast for small or unsorted lists, but it becomes slow as the list grows larger.

Summary

Linear search checks each item one by one and works on any list but can be slow for large lists.

Binary search works only on sorted lists and finds items faster by dividing the list in half repeatedly.

Choosing the right search method depends on whether the list is sorted and how large it is.