package main

// ??? so many problems here
/* func search(nums []int, target int) bool {
	if len(nums) == 0 {
		return false
	}
	beg, end := 0, len(nums)-1
	var mid int
	// how to find the smallest num of arr?
	for beg < end {
		mid = (beg + end) / 2
		if nums[mid] > nums[end] {
			beg = mid + 1
		} else if nums[mid] < nums[end] {
			end = mid - 1
		} else {
			for nums[mid] < nums[(mid+1)%len(nums)] {
				mid = (mid + len(nums) - 1) % len(nums)
			}
			break
		}
	}
	fmt.Println(mid)
	if target == nums[mid] {
		return true
	}
	if target < nums[0] {
		beg, end = mid+1, len(nums)-1
	} else {
		beg, end = 0, mid-1
	}
	for beg <= end {
		mid = (beg + end) / 2
		if target < nums[mid] {
			end = mid - 1
		} else if target > nums[mid] {
			beg = mid + 1
		} else {
			return true
		}
	}
	return false
} */

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