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

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 01:

$ cd path/to/cse-30872-su23-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-su23/challenge04
{"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 teaching assistant.


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