Home Accounts Setup Verify Play Hacks

Gaheera Babbar Binary Search Algorithms HW Hacks

Big Idea Binary Search Algorithms HW Hacks

• 3 min read

Python

Popcorn Hack 1: Which of the following conditions mut be met in order for the procedure to work as intended?

C. The values in the numList must be in sorted order. This is so that the function is able to successfully identify and eliminate half of the lift in each step.

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.

Incorrect: A. Binary search takes more time on average than linear search. Because Binary Search eliminates half of the list in each step, it is more time efficient than Linear Search. While Binary search has a time complexity of O(log n), linear search has a time complexity of O(n).

Correct: B. Binary search cannot be used on unsorted lists without modifications. The list must be sorted in order for Binary Search to successfully eliminate half of the list.

Incorrect: C. Binary search always returns the first occurrence of the target. Standard binary search simply returns any one occurrence, not specifically the first. Unless it’s explicitly modified, it may return the middle or some other occurrence. Incorrect: D. Binary search can only be used on lists with unique values. Binary search works on lists with duplicate values, but theysometimes must be modified if searching for the first or last occurrence of a value. It does not require all elements to be unique.

Popcorn Hack 3

[‘a’, ‘b’, ‘c’, ‘d’, ‘e’, ‘f’, ‘g’] Code a binary search algorithm in your notebook that returns the index when given an element of the array (eg. an input of ‘c’ should return 2).

def binary_search(arr, target):
    left = 0
    right = 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  # Return -1 if target is not found

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 = 0
    right = 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 

search_prices = [1.25, 6.49, 10.00]

for price in search_prices:
    result = binary_search(price_list, price)
    if result != -1:
        print(f"Price ${price:.2f} was found at index {result} in the sorted list.")
    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 at index 3 in the sorted list.
Price $6.49 was found at index 12 in the sorted list.
Price $10.00 was NOT found in the dataset.