Problem $2.$ Imagine you're scrolling through your camera roll, trying to find that one perfect selfie you took

a month ago. Instead of swiping through hundreds of photos, you can jump to the middle of the roll. You can

remember if the selfie you're looking for was taken before this middle point, so you only need to check the earlier

photos. If it's after, you focus on the later ones. Each time, you cut the number of photos you need to scroll through

in half, until you find that perfect shot.

This is exactly how binary search works: it checks the midpoint of a sorted array $($in this case, your photo roll$)$

and eliminates half of the options from further consideration, repeating this process until the target is found.

Observe that the binary search algorithm repeats this procedure, halving the size of the remaining portion of

the subarray each time.

Write recursive pseudocode for binary search and give a small example $($using a sorted array of $5$ elements$).$

Argue that the worst$-$case running time of binary search is $O(logn).$