Question 1 (15 marks) In the class we have discussed how the binary search works and importance of using invariant or assertions to verify our program. In this problem we will be using assertions in our binary search program. Throughout this question, please refer to the Lecture 12 slide titled Binary Search Code, which shows a version of the binary search implemented using a while loop; the code excerpts in this question are taken from that slide. a) What should be the first check or invariant when we implement binary search? Hint: this is a condition on the array required for using binary search (but not for linear search). Write an assertion for your condition by filling in the blank inside the assert command with a function call, and implement the function that assert calls to check the invariant. int BinarySearch(int arr[], int len, int target) { assert( ________ ); } b) What must be true about target right after the while loop? Write a possible loop invariant for this step in the form of an assert statement. Simply write the logical condition inside the assert command. Hint: this can be done through a short, one-line expression, and no function is necessary. int BinarySearch(int arr[], int len, int target) { while (first <= last) { assert( ________ ); int mid = (first+last) / 2; } } c) Make a short argument (4-5 sentences) to show that the Binary Search code (version with while loop) from class terminates. Hint: Think about what happens to the values of first and/or last after every iteration in the while loop.

This is from the slide (sorry forgot to include it):

int BinarySearch(int arr[], int len, int target) {

int first = 0;

int last = len-1;

while(first <= last) {

// whats a good assertion here?

int mid = (first+last) / 2;

if (target == arr[mid]) return mid;

if (target < arr[mid]) last = mid-1;

else first = mid+1;

}

return -1;

}