Binary Search #

This lab introduces an alternate technique for searching for an item in a list, binary search.

Syllabus Topics [SL] #

• B2.4.2 Construct and trace algorithms to implement a linear search and a binary search for data retrieval.

Key Vocabulary #

[0] Set up #

💻 Go into your unit folder and clone your repo. Be sure to replace yourGithubUsername with your actual username.

cd ~/desktop/dpcs/unit02_data_structures
git clone https://github.com/isf-dp-cs/lab_binary_search_yourGithubUsername

cd lab_binary_search_yourGithubUsername

💻 Enter the Poetry Shell to start the lab. As a reminder, we will run this command at the start of each lab, but only when we are inside a lab folder.

poetry shell

👾 💬 Exiting the poetry shell

When you want to exit the shell, you can type exit or ^D

[1] Binary Search #

Overview of the algorithm:

Specifics on the algorithm steps:

📖 Here are the key steps the algorithm.

`high` is the index at the end of the search area
`low` is the index at beginning of the search area
`mid` is the average of `high` and `low` 

keep looping until `low` is bigger than `high`
    `current` is the value located at `mid`
    if `current` is the `target` value
        return `mid`
    else if `current` is higher than the `target` value
        update `high`
    else
        update `mid`

Code Binary Search #

💻 In search.py, write the function binary_search().

💻 In binary_search(), include a counter variable for each step it takes to find the target value. Output it like so:

Binary 17/370105

💻 Run your function using the test data at the bottom of the file.

📝 Practice Coding by Hand

1. Take out a piece of paper and write out entire the function for binary_search() without looking at your solution.

2. Double check your handwritten code against your typed code.

3. If you made mistakes, take note of them and fix your handwritten code.

4. Hand your written code it in to a teacher

[2] Linear Search #

📖 Here are the key steps the algorithm.

iterate through the list
    if the current element is the target value, return index
    repeat until target element is found or until you reach the end of the list

Code Linear Search #

💻 In search.py, write the function linear_search().

💻 In linear_search(), include a counter variable for each step it takes to find the target value. Output it like so:

Linear 263041/370105

💻 Run your function using the test data at the bottom of the file.

[3] Runtime tests #

💻 In runtime_test.py, write construct code to run 10 tests using the word_list and output the average times for binary search and linear search. For each test, it should search for a random word from word_list.

The final output should look something like this:

Running Tests: 100%|███████████████████████████| 10/10 [00:00<00:00, 216.08it/s]
average time elapsed binary: 0.00000575 seconds
average time elapsed linear: 0.00461342 seconds

💻 You can create a progress bar to follow which test it is on using the tqdm library.

for i in tqdm(range(10), desc="Running Tests"):    

💻 Be sure to run the test multiple times. Then, try increasing the number of tests. What do you notice about the average times and step ratio?

[4] Deliverables #

⚡✨ Once you complete the lab, be sure to complete these two steps:

📋 Update Syllabus Tracker: Go to your Syllabus Content Checklist in your Google Drive and update it accordingly.

💻 Push your work to Github

• git status
• git add -A
• git status
• git commit -m “describe your code here”
• git push
• remote

[5] Extension #

SL+HL: Practice handwriting #

📝 Practice Coding by Hand

1. Take out a piece of paper and write out entire the function for linear_search() and for binary_search() without looking at your solution.

2. Double check your handwritten code against your typed code.

3. If you made mistakes, take note of them and fix your handwritten code.

4. Hand in your written code to your teacher

SL+HL: Test Questions #

✏️ Brainstorm potential test questions for this syllabus topic using these command terms: state, define, identify, explain, construct

B2.4.2 - Construct and trace algorithms to implement a linear search and a binary search for data retrieval.

✏️ Add your question to the google form

✏️ Answer your potential test questions & check with a peer/teacher.

HL only: Binary Search Recursive #

You can solve binary search recursively two ways - one uses indexes to track your progress, or we can use our usual slicing technique.

Recursive with indexes #

💻 In search.py, write the function bin_search_recursive(low, high, target, list).

• the low and high parameters should be indexes
• the list does not be sliced or altered in this solution. instead, alter low and high to approach the base case

💻 In runtime_test.py, add in a test for bin_search_recursive()

Recursive with slicing #

💻 In search.py, write the function bin_search_recursive_slicing(target, list).

• this time, use slicing to approach the base case 💻 In runtime_test.py, add in a test for bin_search_recursive_slicing()

💻 Push your work to Github.