Assignment: Develop common methods on data structure using a restricted array. restricted_array.rb provides the RestrictedArray class to be used. RestrictedArray allows you to:
- Create an integer array of default size (i.e. chosen randomly from 1-20, inclusive) or of the size provided in the parameter. All integer values are randomly initialized in the range of 1-221. All integer values are randomly initialized in the range of 1 to (200 + size provided), inclusive.
- Get the value at a given index using
array[index]format. Accessing the array at an index less than 0 or greater than its size returnsnil. - Update the value at a given index using
array[index]format. Attempts to update the array at an index less than 0 or greater than its size are ignored.
None of the other methods available in the Ruby Array class are available in the RestrictedArray class.
Due Monday Sept 9th
Implement each of the methods in using_restricted_array.rb. Above each method, elaborate the comment to explain the time and space complexity. If you define the time and space complexity in terms of n, be sure to explain what n stands for.
Methods to implement are:
- length - which calculates the length of the integer array and returns it.
Note: The restricted_array is terminated by
nili.e.array[length] = nil - print_array - which prints each integer value separated by space on the same line
- reverse - which reverses the values in the array in place
- search - which looks for a given integer value in the array. Returns true if found, false otherwise. Note: do not assume that the array is sorted.
- binary_search - which looks for a given integer value in the array. Returns true if found, false otherwise. Note: Assume that the array is sorted in ascending order.
- find_largest - Finds and returns the largest value element in the integer array.
- find_smallest - Finds and returns the smallest value element in the integer array.
For each method, add a comment above it to explain the time complexity and the space complexity of each method.