Suppose you are given the following inputs: a sorted array A$,$ containing n distinct

integers, a lower bound l$,$ and an upper bound u$,$ where l and u might not be in the array A$.$

Design a divide & conquer algorithm in O$($log n$)$ to find the number of elements in A between l

and u$,$ inclusive. Make sure to justify the algorithm$$s correctness and the time complexity $($using

Master$$s Theorem$).$

$($a$.)$ Describe your algorithm in plain english.

Solution: $[$Write your answer here$]$

$($b$.)$ Argue that your algorithm correctly transforms the input to the correct outputs.

Solution: $[$Write your answer here$]$

$($c$.)$ Give the runtime of your algorithm and explain the reasoning.