CS412-Applied-Algorithms/Circular-Search/README.md

# 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](https://canvas.jmu.edu/courses/2112008/files/178177051?wrap=1)

## 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.

<table>
    <tr>
        <td>Sample Input</td>
        <td>Sample Output</td>
    </tr>
    <tr>
        <td><pre>8 10 1 3 6 7<br>6</pre></td>
        <td><pre>4</pre></td>
    </tr>
    <tr>
        <td><pre>6 7 1 2 4 5<br>3</pre></td>
        <td><pre>-1</pre></td>
    </tr>
</table>

### Turning it in

Save your solution **cs412_circular_sort_search.py** and turn it in to
Gradescope.