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 return its index, otherwise return `-1`.

You may assume no duplicate exists in the array.

Your algorithm's runtime complexity must be in the order of O(log n).

``````Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1``````

Solution:

``````func search(nums []int, target int) int {
lenN := len(nums)

if lenN == 0 {
return -1
}
if lenN == 1 {
if nums == target {
return 0
}
if nums != target {
return -1
}
}

start, end := 0, lenN-1

for start+1 < end { //!!
mid :=  (end+start) /2

if nums[mid] == target {
return mid
}
if nums[start] < nums[mid]{  // before pivote side
if nums[start] <= target && target <= nums[mid] {
end = mid
}else {
start = mid
}
} else { // after pivote side
if nums[mid] <= target && target <= nums[end] {
start = mid
} else {
end = mid
}
}
}

if nums[start] == target{
return start
}
if nums[end] == target {
return end
}
return -1
}``````