Popcorn Hack #1

The condition that must be met for the BinarySearch(numList, target) procedure to work correctly is that the values in numList must be in sorted order. Binary search operates by repeatedly dividing the list in half and comparing the target value to the middle element. This process only works correctly if the list is sorted, because the algorithm relies on the order of the elements to determine whether to continue searching in the left or right half. If the list is not sorted, the comparisons would not provide meaningful direction, and the algorithm could fail to find the target even if it exists in the list.

Popcorn Hack #2

The correct answer is Binary search cannot be used on unsorted lists without modifications. This is a key disadvantage because binary search relies on the list being sorted to function correctly. Without a sorted list, it may give incorrect results or fail to find the target entirely. The other options are incorrect: a is false because binary search is typically faster than linear search; c is incorrect because binary search does not guarantee finding the first occurrence when duplicates are present; and d is false because binary search works with duplicate values and does not require all elements to be unique.

Popcorn Hack #3

def binary_search(arr, target):
low = 0
high = 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  # target not found

Example usage:

letters = [‘a’, ‘b’, ‘c’, ‘d’, ‘e’, ‘f’, ‘g’] print(binary_search(letters, ‘c’)) # Output: 2

Homework Hack

import pandas as pd
import math
# 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))
def binary_search(list, value):
    start = 0
    end = len(list)-1

    def search(start, end):
        index = math.floor((end+start)/2)
        if list[index] == value:
            return index
        if list[index] > value:
            return search(start, index-1)
        if index == end and list[index] != value:
            return -1
        else:
            return search(index+1, end)

    return search(start, end)

prices_to_find = [1.25, 6.49, 10.00]

for price in prices_to_find:
    price_index = binary_search(price_list, price)
    if price_index == -1:
        print("Price not found: $" + str(price))
    else:
        print("Price $" + str(price) + " found at index:", price_index)

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
Price $6.49 found at index: 12
Price not found: $10.0

Explanation

The code loads a CSV dataset with product prices using Pandas. It removes rows with missing data using dropna(), then sorts the products by price. The sorted prices are extracted into a list called price_list. A binary search function is defined to search for specific price values efficiently. The function is then used to check for the presence of three specific prices: 1.25, 6.49, and 10.00. The results are printed, showing whether each price was found or not.

Group 7 Homework

Binary Search