kienonline19

Binary Search Exam Questions (Easy–Medium)

1. Basic binary search. Given a sorted list of integers arr and an integer target that is guaranteed to be in arr, write a function binary_search(arr, target) that returns the index of target in O(log n) time. Include loop invariants or a short explanation of why the algorithm is correct. (Based on the binary search exercise in Lecture 6.)

2. Binary search trace. For the list arr = [2, 5, 7, 9, 12, 16, 21, 27] and target = 16, show every iteration of binary search (low, mid, high, and the comparison result) until the target is found. State the number of iterations. (Based on Lecture 4’s binary search visualization.)

3. Index of first False. An array of booleans starts with some True values followed by False values, e.g., [True, True, True, False, False]. Write a function that returns the index of the first False in O(log n) time using binary search. (Based on Lecture 9’s “find first false” exercise.)

4. **Binary search with