Challenge 04: Sam's Search

Not content with a job at a hot Silicon Valley startup, Sam is still grinding hard on LeetCode challenges¹ 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 of unique numbers sorted in ascending order is rotated at some pivot unknown to you beforehand.

For instance, [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.

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-30872-su24-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/check.py script or curl:

$ .scripts/check.py
Checking challenge04 program.cpp ...
  Result Success
    Time 0.16
   Score 6.00 / 6.00

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