Binary hw

`#### Binary HW

Popcorn Hack #1

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

Correct answer: C
Binary Search works by splitting the search space in half repeatedly.
To do that, the algorithm needs to know whether to search the left or right half of the list based on the middle value. This only makes sense if the list is sorted.

---

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

Correct answer: B
Binary search requires a sorted list to work properly.
If the list is unsorted, binary search might go the wrong way when it compares the target to the middle value.

---

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  # Target found, return index
        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

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


def binary_search(arr, target):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid  # Found target, return index
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1  # Target not found


targets = [1.25, 6.49, 10.00]

for price in targets:
    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 list.")

Output

First few rows of sorted data:
      Product  Price
13  Paper Clips   0.89
5       Eraser   0.50
2       Pencil   0.99
9   Glue Stick   1.25
14        Tape   1.75
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 11 in the sorted list.
Price 10.0 not found in the list.

`