Binary Search Homework and Popcorn hacks

Popcorn Hack #1

C, becauwse it needs to be in a sorted order because the binary search algorithm relies on it. The binary search algorithm works by dividing the list in half and checking if the target value is in the left or right half. If the list is not sorted, the algorithm may not work correctly, leading to incorrect results.

Popcorn Hack #2

A is incorrect becuse binary search alogorithms are much faster than linear search algorithms. Binary search algorithms have a time complexity of O(log n), while linear search algorithms have a time complexity of O(n). This means that binary search algorithms can find the target value much faster in large lists compared to linear search algorithms.

B is correct beause a binary serach must use a sorted list. If the list is not sorted, the binary search algorithm will not work correctly. The algorithm relies on the fact that the list is sorted to divide it in half and check if the target value is in the left or right half.

C is incorrect because while binary search algorithms return the first iteration of the target value, linear search alogirthms do the same. Both algorithms will return the first occurrence of the target value in the list. However, binary search algorithms are more efficient in finding the target value in large lists compared to linear search algorithms.

D is incorrect because binary search algorithms can use non unique values. The algorithm will still work correctly and return the first occurrence of the target value in the list, regardless of whether the list contains unique or non-unique values.

Popcorn Hack #3

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

letters = ['a', 'b', 'c', 'd', 'e', 'f', 'g']
target = 'g'
result = binary_search(letters, target)
print(f"Index of '{target}': {result}")

Index of 'g': 6

Homework Hack

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()

# Preview the sorted data
print("First few rows of sorted data:")
print(data_sorted.head())
print("Original row count:", len(data))
print("Cleaned row count:", len(data_cleaned))

# Binary search function
def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# Prices to search for
prices_to_search = [1.25, 6.49, 10.00]

# Search for each price and print results
for price in prices_to_search:
    index = binary_search(price_list, price)
    if index != -1:
        print(f"Price {price} found at index {index} in the sorted list.")
    else:
        print(f"Price {price} not found in the sorted 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 found at index 3 in the sorted list.
Price 6.49 found at index 12 in the sorted list.
Price 10.0 not found in the sorted list.