adiktt#2

Popcorn Hack 1

The procedure BinarySearch(numList, target) correctly implements a binary search algorithm on the list of numbers numList. The procedure returns an index where target occurs in numList, or -1 if target does not occur in numList.

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

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

Explanation:
Binary search only works correctly when the list is in sorted order. It relies on comparing the target with the middle value to decide whether to search the left or right half. If the list isn’t sorted, this logic breaks down and the algorithm may miss the correct value or behave unpredictably.

• A is incorrect – Binary search works on lists of any length, even or odd.
• B is incorrect – Duplicates are allowed; binary search can still return one occurrence.
• D is incorrect – The target can be -1. That’s not a restriction. -1 is just used as a return value when the target isn’t found.

Popcorn Hack 2

Which of the following statements correctly describes a disadvantage of binary search compared to linear search?

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

Explanation:
Binary search requires the list to be sorted. This is its main limitation compared to linear search, which can work on any list, sorted or not. If you try to apply binary search to an unsorted list without modifying it (e.g., by sorting it first), it may give incorrect results or fail to find the target altogether.

---

Why the other options are wrong:

• A is incorrect – Binary search is faster than linear search on average, especially for large lists (O(log n) vs. O(n)).
• C is incorrect – Binary search does not guarantee the first occurrence in a list with duplicates. It returns an occurrence, which might not be the first.
• D is incorrect – Binary search works fine with duplicate values; the list doesn’t need to have only unique values.

Popcorn Hack 3

Given the sorted list:

['a', 'b', 'c', 'd', 'e', 'f', 'g']




```python
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 the target
        elif arr[mid] < target:
            low = mid + 1  # Search in the right half
        else:
            high = mid - 1  # Search in the left half

    return -1  # Target not found

# Test example
letters = ['a', 'b', 'c', 'd', 'e', 'f', 'g']
print(binary_search(letters, 'c'))  # Output: 2

2

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