Assignment 1

Deadline: Nov, 11 2022 14:00 CET

Grading

You are provided with tests that will run every time your code is pushed. You can see their results and observe what is failing and how. You can also run these tests using your IDE terminal by calling pytest <test_file_name>. Tests can also be ran individually by calling pytest <test_file_name>::<test_name>

Exercises

1.1 Finding where a sorted array has been rotated

Implement the function find_rotation(). This takes a sequence, which represents an array that was sorted and now has been rotated. Rotating an array means that we move the first n elements to the end. For example, [12, 20, 200, 2, 10] is a rotated array where the first two elements have been removed from the beginning and appended at the end. The index of the rotation in this example is 3. Your function should return the index of the rotation. Should there be no rotation (that is, if the array is already sorted), return -1

You should implement this by means of a recursive binary search. For this, there are also two optional parameters start and end which you may make use of.

1.2 Implement a ternary search

Given a sorted sequence to look in and a value to look for, implement a recursive ternary search that returns the index at which the value has been found. If the value is not in the sequence, ternary_search should return -1.

A ternary search uses the same ideas as a binary search, but instead of dividing the input into two parts, it does so into three.

Wrapping up

Do not forget to

• indicate your name(s) in the file header
• add the honor code (I/We pledge that this code represents my/our own work)
• commit all your changes
• push it to your GitHub repository