func search(nums []int, target int) int {
    if len(nums) == 0 {
        return -1
    }
    var minIndex int
    min := nums[0]
    for i, num := range nums {
        if i == 0 {
            continue
        }
        if min > num {
            min = num
            minIndex = i
        }
    }
    var maxIndex, max int
    if minIndex == 0 {
        maxIndex = len(nums) - 1
    } else {
        maxIndex = minIndex - 1
    }
    max = nums[maxIndex]
    if target < min {
        return -1
    } else if target > max {
        return -1
    }

    if min == target {
        return minIndex
    } else if max == target {
        return maxIndex
    }
    if minIndex == maxIndex {
        return -1
    }

    offset := minIndex - 0
    middleIndex := (len(nums) + 1) / 2 - 1 + offset
    if middleIndex >= len(nums) {
        middleIndex = middleIndex - len(nums)
    }
    if middleIndex >= 0 && middleIndex < len(nums) {
        middle := nums[middleIndex]
        if middle == target {
            return middleIndex
        } else if middle > target {
            if middleIndex >= minIndex {
                result := search(nums[minIndex:middleIndex], target)
                if result == -1 {
                    return -1
                }
                return result + minIndex
            }
            right := search(nums[minIndex:], target)
            if right != -1 {
                return right + minIndex
            }
            left := search(nums[:middleIndex], target)
            return left
        } else {
            if middleIndex <= maxIndex {
                result := search(nums[middleIndex:maxIndex], target)
                if result == -1 {
                    return -1
                }
                return result + middleIndex
            } else {
                right := search(nums[middleIndex:], target)
                if right != -1 {
                    return right + middleIndex
                }
                left := search(nums[:maxIndex], target)
                return left
            }
        }
    }

    return -1
}