Challenge 04: Sam's Search

Not content with an internship at a hot Silicon Valley startup, Sam has been grinding hard on LeetCode challenges¹. In fact, he was geeking out on their 30-day Challenge during the month of April 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.

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

Submission

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

$ cd path/to/cse-34872-su20-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 challenge04               # Create and checkout challenge04 branch

$ $EDITOR challenge04/program.cpp           # Edit your code

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

$ git push -u origin challenge04            # Send changes to GitHub

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

$ .scripts/submit.py
Submitting challenge04 assignment ...
Submitting challenge04 code ...
  Result Success
   Score 6.00
    Time 0.16

$ curl -F source=@challenge04/program.cpp https://dredd.h4x0r.space/code/cse-34872-su20/challenge04
{"result": "Success", "score": 6, "time": 0.16451787948608398}