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.

Retrieved from http://www.cs.rpi.edu/~zaki/www-new/pmwiki.php/IntroAlgorithms/Lab0

Page last modified on January 16, 2018, at 08:22 AM