zulily Interview Questions

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

You are given a target value to search. If the value is in the array, then return its index; otherwise, return -1. 

Notes:

• Rotating an array at pivot $n$ gives you a new array that begins with the elements after position $n$ and ends with the elements up to position $n$.
• You may assume no duplicate exists in the array.

Bonus: Your algorithm’s runtime complexity should be in the order of $O(\log n)$.

Example:

Input: 

sample_input = [0,1,2,4,5,6,7]  
rotated_input = [4,5,6,7,0,1,2]
target_value = 6

Output:

def target_value_search(rotated_input, target_value) -> 2