3.11 Popcorn Hacks

Pocorn Hack 1 (from CB MC 2020)

• The procedure BinarySearch(numList, target) correctly implements a binary search algorithm on the list of numbers numList. The procedure returns an index here 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? Explain why.

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

The correct answer is c because binary search has to be sorted in order to filter in an order that eliminates halves.

---

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.

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

My answer:

a) Wrong because Binary search is faster on average than linear search because it halves the search space each step. b) Right, Binary search requires the list to be sorted, so it can’t be used on unsorted lists without modifications. c) Wrong because Binary search does not guarantee the first occurrence is returned in a list with duplicates unless specifically implemented to do so. d) Wrong because Binary search works with duplicate values as long as the list is sorted; uniqueness is not required.

---

Popcorn Hack 3

Given the sorted list:

['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).

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

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
binary_search_strings(arr, 'c')  # Example usage

2