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[0] == target {
return 0
}
if nums[0] != 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
}
```