Popcorn Hack 1
Which of the following conditions must be met in order for the procedure to work as intended? Explain why.
a) The length of numList must be even
b) The list numList must not contain any duplicates
c) The values in numList must be in sorted order
d) The value of the target must not be equal to -1
This is the answer because if the list is not sorted, we don’t know necessary if everything is in this or that half. This is because if we remove half of the list and it isn’t sorted, then we don’t know if our target is in the half we removed or the half we didn’t. The other answer choices are just false.
Popcorn Hack 2
Which of the following 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
The answer is correct for the same reason it was on the first question. Number A was wrong because binary search is on a logarithmic scale so it is much faster than linear search. Answer choice C is wrong because linear search is the one that does this and binary search can be modified to not do this. Answer choice D is wrong because it can be used on lists with duplicate values as long as they are ordered.
Popcorn Hack 3
arr = ['a', 'b', 'c', 'd', 'e', 'f', 'g']
def binary_search_strings(arr, target):
low, high = 0, len(arr) - 1
while low <= high:
mid = (low + high) // 2
guess = arr[mid]
if guess == target:
return mid # Found it!
elif guess < target:
low = mid + 1 # Target comes after mid
else:
high = mid - 1 # Target comes before mid
return -1 # Not found
binary_search_strings(arr, 'c')
2
Homework Hack
import pandas as pd
data = pd.read_csv("school_supplies.csv")
data_cleaned = data.dropna()
data_sorted = data_cleaned.sort_values(by="Price")
price_list = data_sorted["Price"].tolist()
print("First few rows of sorted data:")
print(data_sorted.head())
print("Original row count:", len(data))
print("Cleaned row count:", len(data_cleaned))
def binary_search(prices, target):
left, right = 0, len(prices) - 1
while left <= right:
mid = (left + right) // 2
if prices[mid] == target:
return True
elif prices[mid] < target:
left = mid + 1
else:
right = mid - 1
return False
search_prices = [1.25, 6.49, 10.00]
for price in search_prices:
found = binary_search(price_list, price)
if found:
print(f"Price ${price:.2f} was FOUND in the list.")
else:
print(f"Price ${price:.2f} was NOT FOUND in the list.")
First few rows of sorted data:
Product Price
5 Eraser 0.50
14 Paper Clips 0.89
2 Pencil 0.99
9 Glue Stick 1.25
1 Pen 1.50
Original row count: 15
Cleaned row count: 15
Price $1.25 was FOUND in the list.
Price $6.49 was FOUND in the list.
Price $10.00 was NOT FOUND in the list.