Question $1$: $(40$ points$)$

Binary search is an efficient algorithm that searches for an element in a sorted array.

Since the array is sorted, the search complexity is reduced from $O(n)$ for the naive linear

search to $O(logn)$ for binary search. To achieve that, the algorithm searches a sorted

array by repeatedly dividing the search interval in half $($Figure $1).$

Searching for $17$ in this $10-$element array

Figure $1$: An example illustrating the binary search algorithm.

Below is a program in C that implements binary search. In this question though,

you are required to write the equivalent x$86-64$ assembly program for the procedure

binarySearch. Your implementation must follow all the x$86-64$ calling conventions for

saving$/$restoring registers. Please note that int in C represents a signed $32-$bit value.