Popcorn Hack 1
c
The answer is c because if the list is not sorted, the algorithm cannot make accurate eliminations of a half (as the number it comes across may be smaller than the target, but the target could be on the wrong side of the list).
Popcorn Hack 2
b
The answer is b because an unsorted list could result in an error or incorrect result. The answer is not a because a binary search takes much less time on average than a liner search. The answer is not c because a linear search also only returns the first occurence of the target. The answer is not d because a binary search can be used on lists with repeating values, but it will only give the first occurence of the target.
Popcorn Hack 3
sorted_list = ['a', 'b', 'c', 'd', 'e', 'f', 'g']
def binary_search(arr, target):
low, high = 0, len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
index = binary_search(sorted_list, 'f')
print(index)
5
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())
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
targets = [1.25, 6.49, 10.00]
# Search and print results
for price in targets:
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
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.
Explanation
First, I used pandas with the downloaded school_supplies.csv file and cleaned the data as well as sorted it. Then, I used a binary search algorithm to find the price in the data set.
More depth
I imported pandas, set the dataset as a variable with data=pd.read_csv and then cleaned it and set the cleaned data as a new variable with data_cleaned=data.dropna and then sorted it and set it as a variable with data_sorted=data_cleaned.sort_values and then used a binary search algorithm to find the exact prices in the data set.