Binary Search and the Power of Divide and Conquer

calendar_today June 2, 2025 schedule 6 min read

Learning Objectives: By the end of this lesson, you will be able to:

Explain and implement the binary search algorithm in pseudocode

Understand why binary search requires sorted data

Describe the divide and conquer strategy and its advantages

1. Welcome and Introduction (5 minutes)

Icebreaker Activity

Have you ever looked up a word in a dictionary or searched for a name in a phone book? Did you start at the beginning, or did you jump to the middle and adjust based on what you found?

Lesson Overview

Duration: 60–90 minutes
Prerequisites: Completion of Days 1–9 lessons (especially sorting and searching)
Materials Needed: Pen and paper or a text editor for writing pseudocode

2. Learning Objectives and Session Outline (5 minutes)

What We’ll Cover Today:

Why sorting matters for searching
The binary search algorithm: how it works
The divide and conquer strategy
Step-by-step pseudocode and tracing
Efficiency and limitations of binary search
Hands-on practice and exercises

Success Criteria:

By the end of this session, you should be able to write, trace, and analyze binary search in pseudocode and explain the divide and conquer approach.

3. Foundation Knowledge (15-20 minutes)

Core Concepts

Why Sorting Matters for Searching

Binary search only works on sorted data. Sorting allows you to eliminate half the search space with each step, making searching much faster.

Binary Search Algorithm

Binary search repeatedly divides the list in half, comparing the target to the middle element. If the target is less, search the left half; if more, search the right half. Repeat until found or the list is empty.

Divide and Conquer

Divide and conquer is a strategy where you break a problem into smaller subproblems, solve them, and combine the results. Binary search is a classic example.

Efficiency

Binary search is much faster than linear search for large lists
Reduces the number of comparisons from N (linear) to about log2(N) (binary)

Key Terminology

Binary Search: Searching by repeatedly dividing the list in half
Divide and Conquer: Breaking a problem into smaller parts to solve efficiently
Sorted Data: Data arranged in order (required for binary search)

4. Detailed Explanation and Examples (25-30 minutes)

Understanding Binary Search

Binary search is efficient but only works on sorted lists. Each comparison eliminates half the remaining possibilities.

Practical Applications

Looking up a word in a dictionary
Searching for a record in a sorted database
Finding a value in a sorted array

Common Misconceptions

Misconception: Binary search works on unsorted data. Reality: The list must be sorted for binary search to work.
Misconception: Binary search always finds the item. Reality: If the item is not present, the search ends with failure.

5. Live Coding Demonstration (20-25 minutes)

Example 1: Binary Search in Pseudocode (Iterative)

FUNCTION binarySearch(sortedList, itemToFind)
  SET lowIndex TO 0
  SET highIndex TO LENGTH(sortedList) - 1
  SET found TO FALSE
  WHILE lowIndex <= highIndex AND found IS FALSE DO
    SET middleIndex TO FLOOR((lowIndex + highIndex) / 2)
    IF sortedList[middleIndex] == itemToFind THEN
      SET found TO TRUE
      // Optional: STORE position = middleIndex
    ELSE IF sortedList[middleIndex] < itemToFind THEN
      SET lowIndex TO middleIndex + 1
    ELSE
      SET highIndex TO middleIndex - 1
    ENDIF
  ENDWHILE
  IF found IS TRUE THEN
    // Optional: RETURN position
    RETURN TRUE // Or "Found"
  ELSE
    RETURN FALSE // Or "Not Found"
  ENDIF
ENDFUNCTION

Explanation:

The loop narrows the search range by half each time
Checks the middle element and adjusts the range
Returns TRUE if found, FALSE otherwise

Example 2: Tracing Binary Search

List: [10, 20, 30, 40, 50, 60, 70], Item to find: 20
Track lowIndex, highIndex, and middleIndex at each step
Try with an item not in the list (e.g., 25)

Example 3: Efficiency Comparison

For a list of 1,000,000 items:
- Linear search: up to 1,000,000 comparisons
- Binary search: about 20 comparisons (log2(1,000,000) ≈ 20)

Debugging Demonstration

Common mistake: Forgetting to update lowIndex or highIndex correctly, or using binary search on unsorted data.

// Incorrect
IF sortedList[middleIndex] < itemToFind THEN
  SET highIndex TO middleIndex - 1 // Wrong direction!
// Corrected version
IF sortedList[middleIndex] < itemToFind THEN
  SET lowIndex TO middleIndex + 1
ENDIF

6. Hands-On Practice (20-30 minutes)

Exercise 1: Basic Practice (10 minutes)

Objective: Write pseudocode for binary search that returns the index of the found item, or -1 if not found.

Starter Code:

FUNCTION binarySearch(sortedList, itemToFind)
  // Your steps here
ENDFUNCTION

Solution:

FUNCTION binarySearch(sortedList, itemToFind)
  SET lowIndex TO 0
  SET highIndex TO LENGTH(sortedList) - 1
  WHILE lowIndex <= highIndex DO
    SET middleIndex TO FLOOR((lowIndex + highIndex) / 2)
    IF sortedList[middleIndex] == itemToFind THEN
      RETURN middleIndex
    ELSE IF sortedList[middleIndex] < itemToFind THEN
      SET lowIndex TO middleIndex + 1
    ELSE
      SET highIndex TO middleIndex - 1
    ENDIF
  ENDWHILE
  RETURN -1
ENDFUNCTION

Exercise 2: Intermediate Challenge (10 minutes)

Objective: Trace binary search on [10, 20, 30, 40, 50, 60, 70] for 20 and 25. List the values of lowIndex, highIndex, and middleIndex at each step.

Requirements:

Show the search process for both present and absent items
Explain why binary search fails on unsorted lists

Exercise 3: Creative Application (10 minutes)

Objective: Write pseudocode for a function that counts how many times a value appears in a sorted list using binary search as a starting point.

Extension Ideas:

Modify binary search to return all indices of a value (for duplicates)
Compare binary search to linear search for different list sizes

7. Common Pitfalls and Troubleshooting (10 minutes)

Frequent Mistakes

Problem: Using binary search on unsorted data Cause: Not checking if the list is sorted Solution: Always sort the list first or ensure it is sorted
Problem: Infinite loops or missed items Cause: Incorrectly updating lowIndex or highIndex Solution: Double-check your index updates and loop conditions

Debugging Tips

Trace your algorithm with sample data
Print or track index values at each step
Test with present and absent items

8. Best Practices and Professional Tips (5 minutes)

Industry Standards

Use binary search for large, sorted datasets
Always check that data is sorted before searching
Analyze and compare efficiency with other algorithms

Next Steps in Your Learning Journey

Learn about recursive binary search
Explore other divide and conquer algorithms (e.g., mergesort)
Practice implementing binary search in a programming language

9. Summary and Review (5 minutes)

Key Takeaways

Binary search is a fast, efficient search algorithm for sorted data
Divide and conquer breaks problems into smaller, manageable parts
Always ensure your data is sorted before using binary search

Quick Review Questions

Why does binary search require sorted data?
How many comparisons does binary search need for a list of 1,000,000 items?
What is the divide and conquer strategy?

For Instructors

Teaching Tips

Use visual aids to show the search range shrinking
Encourage students to trace binary search by hand
Discuss the importance of sorted data and index updates

Assessment Ideas

Have students write and trace binary search for different cases
Peer review: students check each other’s logic and tracing
Short quiz on binary search and divide and conquer

Adaptation Notes

For advanced students, introduce recursive binary search or other divide and conquer algorithms
For online delivery, use interactive search visualizations
Adjust timing based on student engagement and questions