Embercode: AI-powered software engineer course

1. What does this code print? ``

python
a = [2, 4, 4, 4, 7, 9, 12]
lo = 0
hi = len(a)
while lo < hi:
    mid = lo + (hi - lo) // 2
    if a[mid] >= 9:
        hi = mid
    else:
        lo = mid + 1
print(lo)

``

4756

2. What does this code print? ``

python
lo = 1_500_000_000
hi = 2_000_000_000
print((lo + hi) / 2)

``

1750000000.01750000000-3974836483500000000.0

3. This find_exact function loops forever on [1, 5] with target 9. What is the bug? ``

python
def find_exact(a: list[int], target: int) -> int:
    lo = 0
    hi = len(a) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if a[mid] == target:
            return mid
        if a[mid] < target:
            lo = mid
        else:
            hi = mid - 1
    return -1

``

lo = mid keeps mid in the range, so when a[mid] is less than the target the range may never shrinkhi starts at len(a), so the loop reads past the end of the listThe return -1 is inside the loop, so the search ends too earlyThe loop should use lo < hi, so the range can never become empty

4. This least_feasible is called as least_feasible(0, len(a), lambda i: a[i] >= 4) on a = [2, 4, 4, 4, 7, 9, 12]. It returns 0, but the first yes is at index 1. What is the bug? ``

python
def least_feasible(lo: int, hi: int, ok: Callable[[int], bool]) -> int:
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if ok(mid):
            hi = mid - 1
        else:
            lo = mid + 1
    return lo

``

lo should start at 1, not 0The loop condition should be lo <= hiThe check should be a[i] > 4, not >= 4hi = mid - 1 throws away mid, which may be the first yes, so the answer can be skipped

5. Write the Python expression for the middle index that starts at lo and adds half the distance from lo to hi, using floor division. Write only the expression, without mid =.

Type your answer.

Binary search in Python