Binary Search

Popcorn Hacks and Homework Hacks

• 2 min read

Popcorn Hack #1

Which of the following conditions must be met in order for the procedure to work as intended? Explain why.

C. The values in numList must be in sorted order

Since the algorithm is bounded from lowest to highest and then loops from high to low, the values must be in order.

Popcorn hack #2

Why 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.

B. Binary search cannot be used on unsorted lists without modifcations

Binary search needs to have a sorted array for the splitting system to work.

Popcorn hack #3

Code a binary search algo in your notebook that returns index when given an element of the array

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 


letters = ['a', 'b', 'c', 'd', 'e', 'f', 'g']
print(binary_search_char(letters, 'e'))  



4

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

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

search_prices = [1.25, 6.49, 10.00]

for price in search_prices:
    found = binary_search(price_list, price)
    if found:
        print(f"Price ${price:.2f} was FOUND in the dataset.")
    else:
        print(f"Price ${price:.2f} was NOT FOUND in the dataset.")


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 was FOUND in the dataset.
Price $6.49 was FOUND in the dataset.
Price $10.00 was NOT FOUND in the dataset.

The file with school supplies was loaded, and rows with missing values were removed. The data was sorted by price, and a list of specific prices was searched. The search function checked if those prices were found and displayed the results.