Binary Search - Gyutae KIm

Popcorn Hack 1

c) The values in numList must be in sorted order

For the binary search algorithm to work as intended, the list numList must be sorted in ascending or descending order. Binary search works by repeatedly dividing the search interval in half and comparing the middle element to the target value. If the list is not sorted, the algorithm cannot reliably determine whether the target is in the left or right half of the list, leading to incorrect results.

Popcorn Hack 2

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

Binary search requires the list to be sorted in order to function correctly. If the list is unsorted, the algorithm cannot reliably determine whether the target is in the left or right half of the list, making it ineffective.

Popcorn Hack 3

def binary_search(sorted_list, target):
    left = 0
    right = len(sorted_list) - 1

    while left <= right:
        mid = (left + right) // 2
        if sorted_list[mid] == target:
            return mid  # Return the index of the target
        elif sorted_list[mid] < target:
            left = mid + 1  # Search in the right half
        else:
            right = mid - 1  # Search in the left half

    return -1  # Return -1 if the target is not found

# Example usage
sorted_list = ['a', 'b', 'c', 'd', 'e', 'f', 'g']
target = 'c'
result = binary_search(sorted_list, target)
print(f"The index of '{target}' is: {result}")

The index of 'c' is: 2

HW 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(sorted_list, target):
    left = 0
    right = len(sorted_list) - 1

    while left <= right:
        mid = (left + right) // 2
        if sorted_list[mid] == target:
            return mid  # Target found, return index
        elif sorted_list[mid] < target:
            left = mid + 1  # Search in the right half
        else:
            right = mid - 1  # Search in the left half

    return -1  # Target not found

# 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:
    result = binary_search(price_list, price)
    if result != -1:
        print(f"Price {price} found at index {result}.")
    else:
        print(f"Price {price} 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
Price 1.25 found at index 3.
Price 6.49 found at index 12.
Price 10.0 not found.

1. The dataset is loaded using Pandas and cleaned by dropping rows with missing values.
2. The data is sorted by the ‘Price’ column to prepare it for binary search.
3. The sorted ‘Price’ column is extracted as a list for efficient searching.
4. A binary search function is implemented to find specific prices in the sorted list.
5. The function searches for the prices 1.25, 6.49, and 10.00, and prints whether each price was found or not.