Binary search is an algorithm that allows for dividing and conquering to select a target value in a osrted list. Benefit: allows to cut on time to find a value
Popcorn Hack #1: I think the values in the numlist must be in sorted order because you add 1 is thet target estimate is higher than the found and you subtract one is the target estimate is lower than teh found.
Binary search is way more efficient than linear search. Binary Search is logarithmic. Big O notation describes the wort case scenario in an algorithm.
with sorted data?
- linear search
Sorted large list
- binary search
Applications
- searching in sorted records
- games, AI
Popcorn Hack #2 B) binary search cannot be used on unsorted lists without modifications.
The list of strings could be sorted alphabeticaally or lexicography
Popcorn Hack #3
def binary_search_strings(arr, target):
low, high = 0, len(arr) - 1
while low <= high:
mid = (low + high) // 2
guess = arr[mid]
if guess == target:
return mid # Found it!
elif guess < target:
low = mid + 1 # Target comes after mid
else:
high = mid - 1 # Target comes before mid
return -1 # Not found
words = ["a", "b", "c", "d", "e", "f", "g"]
print(binary_search_strings(words, "c"))
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):
low = 0
high = len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return True
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return False
# Prices to search for
search_prices = [1.25, 6.49, 10.00]
# Perform the search and print results
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.")