You are given a sorted integer array, nums, and an integer, target. The array may have been rotated by an arbitrary number. Your task is to find and return the index of target in this array. If target does not exist, return -1.

An original sorted array before rotation is given below:

After rotating this array 6 times, it changes to:

Constraints:

• All values in nums are unique.
• The values in nums are sorted in ascending order.
• The array may have been rotated by some arbitrary number.
• $1 \leq$ nums.length $\leq 1000$
• $-10^4 \leq$ nums[i] $\leq 10^4$
• $-10^4 \leq$ target $\leq 10^4$

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

A naive approach is to traverse the whole array while searching for our target.

We get the required solution, but at what cost? The time complexity is $O(n)$ because we traverse the array only once, and the space complexity is $O(1)$. Let’s see if we can use the modified binary search pattern to design a more efficient solution.