Binary search

Questions 1 to 5 of 8

1. 1. What does this program print? ``cpp #include <iostream> #include <vector> int main() { std::vector<int> a = {3, 6, 9, 14, 21, 30}; int lo = 0, hi = 5; while (lo <= hi) { int mid = lo + (hi - lo) / 2; if (a[mid] == 14) { std::cout << mid << std::endl; return 0; } if (a[mid] < 14) lo = mid + 1; else hi = mid - 1; } std::cout << -1 << std::endl; } ``

   243-1
2. 2. What does this program print? ``cpp #include <iostream> template <typename Pred> int first_true(int n, Pred pred) { int lo = 0; int hi = n; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (pred(mid)) hi = mid; else lo = mid + 1; } return lo; } int main() { int a[] = {1, 4, 4, 9, 9, 9, 15}; std::cout << first_true(7, [&](int i) { return a[i] >= 9; }) << std::endl; } ``

   3496
3. 3. This last_true loop never ends when n is 2 and every check is true. What is the bug? ``cpp template <typename Pred> int last_true(int n, Pred pred) { if (n == 0 || !pred(0)) return -1; int lo = 0; int hi = n - 1; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (pred(mid)) lo = mid; else hi = mid - 1; } return lo; } ``

   The check pred(0) should be pred(1).The middle is rounded down, so mid stays at 0 and lo = mid never moves lo forward. It should round up.hi should start at n instead of n - 1.The else branch should set lo = mid + 1.
4. 4. Calling this find_exact on {2, 5} with target 5 never returns. What is the cause? ``cpp int find_exact(const std::vector<int>& a, int target) { int lo = 0; int hi = static_cast<int>(a.size()) - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; if (a[mid] == target) return mid; if (a[mid] < target) lo = mid; else hi = mid - 1; } return -1; } ``

   The loop should be while (lo < hi).hi should start at a.size() instead of a.size() - 1.The check a[mid] == target should use <=.When a[mid] is too small, lo = mid does not step past mid, so lo stays at 0 forever.
5. 5. In the search range from lo = 5 to hi = 9, what is mid using the formula lo + (hi - lo) / 2?

   Type a number.