Binary Search

Popcorn Hack 1 Question: Which condition must be met for BinarySearch(numList, target) to work?

Answer: ✅ c) The values in numList must be in sorted order

Explanation: Binary Search only works on a sorted list. If the list isn’t sorted, the whole premise of cutting the search space in half fails.

Popcorn Hack 2 Question: Which statement describes a disadvantage of binary search?

Answer: ✅ b) Binary search cannot be used on unsorted lists without modifications

Explanation: Binary search requires a sorted list. Linear search works on any list.

def binary_search_char(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

Test

letters = [‘a’, ‘b’, ‘c’, ‘d’, ‘e’, ‘f’, ‘g’] print(binary_search_char(letters, ‘c’)) # Output: 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 by Price
data_sorted = data_cleaned.sort_values(by="Price")

# Extract sorted Price list
price_list = data_sorted["Price"].tolist()

# Binary Search function
def binary_search_prices(prices, target):
    low, high = 0, len(prices) - 1
    while low <= high:
        mid = (low + high) // 2
        if prices[mid] == target:
            return mid
        elif prices[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

# Prices to search
targets = [1.25, 6.49, 10.00]

# Search and print results
for price in targets:
    result = binary_search_prices(price_list, price)
    if result != -1:
        print(f" Price ${price} found at index {result}.")
    else:
        print(f" Price ${price} not found.")

# Output explanation
print("\n How it works:")
print("1. Dataset is loaded using pandas.")
print("2. Rows with missing values are dropped.")
print("3. Data is sorted by the 'Price' column.")
print("4. Prices are extracted into a list.")
print("5. Binary search is used to find target prices in the sorted list.")