Search: Linear vs. Binary

Search is one of the foundational computer science algorithms. The right search algorithm to use depends on the situation, and often we structure our data explicitly to make searching it performant.

This programming assignment asks you to write two search algorithms on sorted lists of integers: a naive linear search and a recursive binary search. After implementing both, you'll see side-by-side graphs of operation counts and execution times so you can observe how these two algorithms perform on large datasets.

Files

• main.py — Where you write your two search functions. Function signatures are already provided; do not change them. Running this file also prints a small sanity check using each function on a short list.
• search_unit_tests.py — Correctness tests for each function, including edge cases. Run these once your sanity check passes.
• search_full_tests.py — The full performance suite. Runs both functions on lists ranging from 10 to 100,000 elements and plots the results.
• number_generator.py — Helper that builds a randomized sorted list of ascending integers and picks a random target from it.

Getting your own copy

You'll work on your own copy of this project on GitHub so you can commit your changes as you go.

1. On the GitHub page for this repository, click the green Use this template button and choose Create a new repository. This creates a fresh copy of the project under your GitHub account.

2. On your new repository's page, click the green Code button and copy the URL.

3. In a terminal on your computer, clone your copy:

   git clone <the URL you copied>
   cd search_py
   

4. As you make progress, save your work back to GitHub:

   git add .
   git commit -m "describe what you changed"
   git push
   

Getting updates from the teacher

If your teacher updates the starter project (for example, adds new test cases), you can pull those changes into your own copy. You only need to set this up once:

git remote add upstream https://github.com/christianmiley/search_py.git

After that, whenever there are updates to grab:

git fetch upstream
git merge upstream/main

Your own work in main.py won't be touched — the merge just brings in the teacher's changes to the test files.

Setup

This project needs Python 3 and matplotlib (for the graphs at the end of the full suite). Install the dependencies with:

pip install -r requirements.txt

How to run the tests

There are three levels of testing, and you should work through them in order. Each one catches different problems: the sanity check makes sure your functions run at all, the unit tests catch correctness bugs cheaply, and the full suite reveals how the algorithms scale.

1. Sanity check — confirm your functions run on a tiny hand-written example:

   python main.py
   

   This prints the result of each search on a short list. If the output looks reasonable, move on. If something crashes, fix it before going further.

2. Unit tests — check correctness across edge cases:

   python search_unit_tests.py
   

   You should see every case pass for both linear_search and binary_search before moving on.

3. Full test suite — run the performance comparison:

   python search_full_tests.py
   

   This prints per-size timings and operation counts, then opens a window with two graphs comparing the algorithms. The graphs are also saved to results.png in the project folder — usually the window pops up on its own, but if it doesn't (for example, if you're running over SSH or in a stripped- down terminal), open results.png to see them.