Lab 0 (Optional)
This lab is optional: Please do not go to this lab on Wednesday; this lab does not affect any part of your grade.
- Implement Binary Search to find whether a number exists in a given sorted list of numbers. Please read this blog post about bugs in binary search. Test with different input data sets.
- You are given an unsorted read-only array of size n-1, containing all numbers from 1 to n except one. Find which number is missing from this array. Can you write a program which will do this in O(n) time, using only a constant amount of additional memory, without looking at each entry of the array more than once? Note that since the array is read-only, and the memory available to you is much less than n, you cannot just sort the array.