Lab 2: Circular Sort Searching
This lab will be started as an in class activity that can be finished outside of class. However, you should make every effort to complete this in class and the reason we have this assignment during class time is to support you getting help and ideas.
Remember, that you should design how the algorithm will work on paper before coding.
Some sample code showing show to read in a line of numbers and store them as a list of ints can be found here: cs412_reading_input.py
Logarithmic Search in a Circularly Sorted List
A list A[0..(n-1)] is circularly sorted if there is an index i such that the
subarray A[(i+1)..(n-1)] concatenated to the subarray A[0..i] is a sorted
list. For example \{7, 8, 10, 1, 2, 3, 4\} is circularly sorted, since the
subarray A[3..6] concatenated with the subarray A[0..2] is the array
${1, 2, 3, 4, 7, 8,
10}$, which is sorted. Your task is to write a recursive algorithm, which given
a a circularly sorted array with no duplicate values and a query integer q
determines and returns the index of q in the array if it exists, or returns
-1 otherwise. Your algorithm should run in O(log n) time.
Input
The input will consist of two lines. The first line contains a circularly sorted, space separated list of numbers. The second line contains a single query integer.
Output
You should output the index of the query integer (indexing from 0) in the list, if it exists, or -1 if it does not exist in the list.
| Sample Input | Sample Output |
8 10 1 3 6 7 |
4 |
6 7 1 2 4 5 |
-1 |
Turning it in
Save your solution cs412_circular_sort_search.py and turn it in to Gradescope.