Popcorn Hack #1
The procedure BinarySearch(numList, target) correctly implements a binary search algorithm on the list of numbers numList. The procedure returns an index here target occurs in numList, or -1 if target does not occur in numList.
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 duplicate values
c. The values in numList must be in sorted order
d. The value of target must not be equal to -1
My Answer: C - For all of the other options (even, duplicate, -1), the procedure would not affect how the actually performs its function. To work as intended, sorting the values in numList will allow for the procedure to go through each number and output either target or -1.
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
My Answer: B - Similarly to the first question, binary search relies on the list its searching to be sorted. The other options (longer time, first occurence return, unique values) are all incorrect.
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(sorted_list, target):
low = 0
high = len(sorted_list) - 1
while low <= high:
mid = (low + high) // 2 # Find the middle index
if sorted_list[mid] == target:
return mid # Return the index if the target is found
elif sorted_list[mid] < target:
low = mid + 1 # Ignore the left half of the list
else:
high = mid - 1 # Ignore the right half of the list
return -1 # Return -1 if the target is not found
# Example of input 'c'
sorted_list = ['a', 'b', 'c', 'd', 'e', 'f', 'g']
target = 'c'
index = binary_search(sorted_list, target)
print(f"Index of '{target}': {index}")
Index of 'c': 2
import pandas as pd
# Load the dataset
data = pd.read_csv("school_supplies.csv")
# Drop rows with missing values
data_cleaned = data.dropna()
# Sort the data by 'Price'
data_sorted = data_cleaned.sort_values(by="Price")
# Extract sorted prices as a list
price_list = data_sorted["Price"].tolist()
# Binary search function
def binary_search(sorted_list, target):
low = 0
high = len(sorted_list) - 1
while low <= high:
mid = (low + high) // 2
if sorted_list[mid] == target:
return mid # Return the index if the target is found
elif sorted_list[mid] < target:
low = mid + 1 # Ignore the left half of the list
else:
high = mid - 1 # Ignore the right half of the list
return -1 # Return -1 if the target is not found
# Prices to search for
prices_to_search = [1.25, 6.49, 10.00]
for price in prices_to_search:
index = binary_search(price_list, price)
if index != -1:
print(f"Price {price} found at index {index}.")
else:
print(f"Price {price} not found.")
# Preview the sorted data
print("\nFirst few rows of sorted data:")
print(data_sorted.head())
# Original and cleaned row counts
print("\nOriginal row count:", len(data))
print("Cleaned row count:", len(data_cleaned))
Price 1.25 found at index 3.
Price 6.49 found at index 12.
Price 10.0 not found.
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
Explanation
The binary search function looks for a specific value target in a sorted list. It repeatedly divides the list in half and checks the middle value. If the middle value matches the target, it returns the index; otherwise, it continues searching in the appropriate half of the list until it finds the target or the list is exhausted. If not found, it returns -1.