Not content with a job at a hot Silicon Valley startup, Sam is still grinding hard on LeetCode challenges1 in hopes of leveling up to another software engineering gig. In fact, he was geeking out on their 30-day Challenge during the month of May and came across this problem:

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., `[0,1,2,4,5,6,7]` might become `[4,5,6,7,0,1,2]`).

You are given a `target` value to search. If found in the array report its `index`, otherwise report it is not found.

You may assume no duplicates exist in the array.

Because Sam is busy networking with people on LinkedIn, he asks that you repay him for the help he provided you in Systems Programming by coding up a solution to this problem for him.

Note: Your algorithm's runtime complexity must be in the order of `O(log n)`.

#### LeetCode¶

This programming challenge is based on 33. Search in Rotated Sorted Array from LeetCode.

## Input¶

Each input test case will consist of two lines. The first line contains the sorted but rotated `array`, while the second line contains the `target` to search for within the `array`.

Here is an example input:

```4 5 6 7 0 1 2
0
4 5 6 7 0 1 2
3
3 5 1
3
```

## Output¶

For each input test case, you are to output a message in the following format if the `target` is found:

```{target} found at index {index}
```

If the `target` is not in the `array`, then report:

```{target} was not found
```

Here is the output for the example input above:

```0 found at index 4
3 was not found
3 found at index 0
```

#### Algorithmic Complexity¶

For each input test case, your solution should have the following targets:

 Time Complexity `O(log(N))`, where `N` is the length of each input array. Space Complexity `O(log(N))`, where `N` is the length of each input array.

Your solution may be below the targets, but it should not exceed them.

## Submission¶

To submit your work, follow the same procedure you used for Reading 00:

```\$ cd path/to/cse-30872-fa21-assignments     # Go to assignments repository
\$ git checkout master                       # Make sure we are on master
\$ git pull --rebase                         # Pull any changes from GitHub

\$ git checkout -b challenge03               # Create and checkout challenge03 branch

\$ \$EDITOR challenge03/program.cpp           # Edit your code

\$ git add challenge03/program.cpp           # Stage your changes
\$ git commit -m "challenge03: done"         # Commit your changes

\$ git push -u origin challenge03            # Send changes to GitHub
```

To check your code, you can use the `.scripts/check.py` script or curl:

```\$ .scripts/check.py
Checking challenge03 program.cpp ...
Result Success
Time 0.16
Score 6.00 / 6.00

\$ curl -F source=@challenge03/program.cpp https://dredd.h4x0r.space/code/cse-30872-fa21/challenge03
{"result": "Success", "score": 6, "time": 0.16451787948608398, "value": 6, "status": 0}
```

#### Pull Request¶

Once you have committed your work and pushed it to GitHub, remember to create a pull request and assign it to the appropriate teaching assistant from the Reading 02 TA List.

1. You are welcome to do a LeetCode weekly challenge as one of your External programming contests for the course.