Overview

You’ve frequently used Python’s built-in functionality for searching for an item in a list, but how does that actually work? What if the list is already sorted; can you search faster then? Today’s focus will be on two algorithms used for finding an item in unsorted and sorted lists.

Basic Learning Objectives

Before class, you should be able to:

  • Explain the idea of sequential searching
  • Explain the high-level idea of binary search

Advanced Learning Objectives

After class, you should be able to:

  • Implement sequential search
  • Identify the time complexity of sequential searching in the worst case
  • Implement recursive binary search
  • Identify when to use sequential vs. binary search

Resources

You should read/watch the following and complete the embedded checks: