Recent Changes - Search:

Main Page



Piazza Site




edit SideBar

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.

  1. 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.
  2. 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.
Edit - History - Print - Recent Changes - Search
Page last modified on January 16, 2018, at 08:22 AM