package main

func searchOld(nums []int, target int) int {
	for i, v := range nums {
		if v == target {
			return i
		}
	}
	return -1
}

func search(nums []int, target int) int {
	beg, end := 0, len(nums)-1
	mid := -1
	// find the smallest one in nums
	for beg < end {
		mid = (beg + end) / 2
		if nums[mid] > nums[end] {
			beg = mid + 1
		} else {
			end = mid
		}
	}
	if mid == -1 || target == nums[mid] {
		return mid
	}
	// judge which area to search
	if target > nums[len(nums)-1] {
		beg, end = 0, mid-1
	} else {
		beg, end = mid+1, len(nums)-1
	}
	// binary search
	for beg <= end {
		mid = (beg + end) / 2
		if target > nums[mid] {
			beg = mid + 1
		} else if target < nums[mid] {
			end = mid - 1
		} else {
			return mid
		}
	}
	return -1
}

/* func main() {
	a1 := []int{4, 5, 6, 0, 1, 2, 3}
	a2 := []int{1, 3}
	fmt.Println(search(a1, 6))
	fmt.Println(search(a2, 3))
} */