Notes

Definition

An algorithm that allows you to divide and conquer to search for a value within a set.

How

The list or array needs to be sorted before the algorithm starts.
In the actual algorithm: set two bounds, lowest and highest.
Looping from high to low, always trying to find the middle integer.
The goal is to split the area we’re searching in half each time.

Implementing in Python

Define a function to take two parameters.

Why is Binary Search So Fast

Cuts the search space in half at every step.
The divide and conquer strategy dramatically reduces the number of checks.

Big O Notation

Big O notation describes the worst-case performance of an algorithm in terms of input size (n).

popcorn hacks:

College baord MC PPOPCORN HACK 1 = C (the values min numlist must be in sorted order) the array must be in a sorted order because it canoot seearcch the first half of the second half if the target is not gaurnetteed to be in one of the halfs.

College baord MC PPOPCORN HACK 2 = B ( the binary search cannot be used on unsorted lists without modification) Since binary search much search on of the havles of the data sets for the target to be in one guarenteed half it must be sorted, so binary search cannot be used on unsorted lists.

POPCORNHACK 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
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1  # Target not found

# Example usage:
arr = ['a', 'b', 'c', 'd', 'e', 'f', 'g']
print(binary_search(arr, 'c'))  # Output: 2

Homework Hack:

import pandas as pd

# Manually create the dataset from the image
data = pd.DataFrame({
    "Product": ["Notebook", "Pen", "Pencil", "Backpack", "Calculator", "Eraser", "Binder", 
                "Marker", "Scissors", "Glue Stick", "Ruler", "Highlighter", "Stapler", 
                "Tape", "Paper Clips"],
    "Price": [2.99, 1.50, 0.99, 25.00, 15.75, 0.50, 3.99, 2.25, 4.99, 1.25, 1.99, 2.50, 
              6.49, 1.75, 0.89]
})

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

# Binary search function
def binary_search(lst, target):
    low, high = 0, len(lst) - 1
    while low <= high:
        mid = (low + high) // 2
        if lst[mid] == target:
            return True
        elif lst[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return False

# Prices to search
targets = [1.25, 6.49, 10.00]

# Search and print results
for price in targets:
    found = binary_search(price_list, price)
    if found:
        print(f"Price ${price} was found in the list.")
    else:
        print(f"Price ${price} was NOT found in the list.")

# Output preview
print("\nFirst few rows of sorted data:")
print(data_sorted.head())
print("Original row count:", len(data))
print("Cleaned row count:", len(data_cleaned))

Price $1.25 was found in the list.
Price $6.49 was found in the list.
Price $10.0 was NOT found in the list.

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