Popcorn Hack 1 Which of the following conditions must be met in order for the rocedure to work as intended

  • a) The length of numList must be even
  • b) The list numList must not contain any duplicate values
  • c) The values in numList must be in sorted order

  • d) The value of target must not be equal to -1

  • For binary search to work correctly, the list you’re searching must be sorted (either from smallest to biggest or biggest to smallest). That’s because binary search works by checking the middle of the list and deciding whether the target number is to the left or right. If the list isn’t sorted, it won’t know which side to look on, and the search won’t work correctly.

Popcorn Hack 2 Which of the following statements correctly describes a disadvantage of binary search compared to linear search? Explain why your answer is correct and why the others are wrong.

  • a) Binary search takes more time on average than linear search
  • b) Binary search cannot be used on unsorted lists without modifications
  • c) Binary search always returns the first occurrence of the target

  • d) Binary search can only be used on lists with unique values

  • Binary search only works on lists that are already sorted. If you try to run it on an unsorted list, it won’t know which side to look on, so it won’t work correctly. You would either need to sort the list first (which takes extra time) or use a different search method like linear search. This is a big disadvantage compared to linear search, which works fine even on unsorted lists.

Popcorn Hack 3 Given the sorted list:

  • [‘a’, ‘b’, ‘c’, ‘d’, ‘e’, ‘f’, ‘g’]
  • Code a binary search algorithm in your notebook that returns the index when given an element of the array (eg. an input of ‘c’ should return 2).
def binary_search(char_list, target):
    low = 0
    high = len(char_list) - 1

    while low <= high:
        mid = (low + high) // 2
        if char_list[mid] == target:
            return mid  # Found the target, return index
        elif char_list[mid] < target:
            low = mid + 1  # Look in the right half
        else:
            high = mid - 1  # Look in the left half

    return -1  # If not found

# Example usage
char_list = ['a', 'b', 'c', 'd', 'e', 'f', 'g']
print(binary_search(char_list, 'c'))  # Output should be 2
print(binary_search(char_list, 'f'))  # Output should be 5
print(binary_search(char_list, 'z'))  # Output should be -1 (not found)


2
5
-1

Homework Hack 1

  • Dataset Use the file: Dataset

  • Goal Use Pandas to load and sort product prices, then write a binary search function to find specific price values.

  • Instructions

    1. Load the dataset using Pandas.
    2. Drop any rows with missing data.
    3. Sort the data by the Price column.
    4. Extract the sorted Price column as a list.
    5. Implement a binary search function that searches for a price in the list.
    6. Use your function to search for these 3 specific prices:
    7. 1.25
    8. 6.49
    9. 10.00
    10. Print a message that clearly shows if each price was found or not found.
    11. Write a short explanation on how your code works.
import pandas as pd

# Step 1: Load the dataset
data = pd.read_csv("school_supplies.csv")

# Step 2: Drop rows with missing values
data_cleaned = data.dropna()

# Step 3: Sort the data by 'Price'
data_sorted = data_cleaned.sort_values(by="Price")

# Step 4: Extract sorted prices as a list
price_list = data_sorted["Price"].tolist()

# Step 5: Implement the binary search function
def binary_search(sorted_list, target):
    low = 0
    high = len(sorted_list) - 1

    while low <= high:
        mid = (low + high) // 2
        mid_value = sorted_list[mid]

        if mid_value == target:
            return mid  # Target value found at index mid
        elif mid_value < target:
            low = mid + 1  # Search in the right half
        else:
            high = mid - 1  # Search in the left half

    return -1  # Target value not found

# Step 6: Search for specific prices
search_prices = [1.25, 6.49, 10.00]

# Step 7: Print results for each search
for price in search_prices:
    index = binary_search(price_list, price)
    if index != -1:
        print(f"Price {price} found at index {index}.")
    else:
        print(f"Price {price} not found.")


Price 1.25 found at index 3.
Price 6.49 found at index 12.
Price 10.0 not found.
  • ​In this project, I used Python’s pandas library to handle a dataset of school supplies. After loading the data and removing any incomplete entries, I sorted the items by their prices. I then created a binary search function to quickly find specific prices within this sorted list. Using this function, I searched for the prices $1.25, $6.49, and $10.00, and displayed messages indicating whether each price was found in the dataset. This approach showcased how binary search can efficiently locate items in a sorted collection.