package main

import (
	"fmt"
)

func search(nums []int, target int) bool {
	beg, end := 0, len(nums)-1
	// for empty array
	if end == -1 {
		return false
	}
	// check if the target is at the beg or at the end of the arr
	if nums[beg] == target || nums[end] == target {
		return true
	}
	// the array is not rotated
	if nums[beg] < nums[end] {
		return binarySearch(nums, target, beg, end)
	}
	// else find the top of the clip
	for beg < end {
		mid := (beg + end) / 2
		if nums[mid] > nums[beg] {
			beg = mid
		} else if nums[mid] < nums[end] {
			end = mid
		} else {
			// find the top point one by one
			if nums[beg] > nums[beg+1] {
				break
			}
			beg++
		}
	}
	// check the area where the target is in
	if target > nums[0] {
		return binarySearch(nums, target, 0, beg)
	}
	return binarySearch(nums, target, beg+1, len(nums)-1)
}

func binarySearch(nums []int, target, beg, end int) bool {
	for beg <= end {
		mid := (beg + end) / 2
		if nums[mid] > target {
			end = mid - 1
		} else if nums[mid] < target {
			beg = mid + 1
		} else {
			return true
		}
	}
	return false
}

func testSearch(nums []int, target int) {
	isIn := search(nums, target)
	checkAgain := false
	for _, num := range nums {
		if num == target {
			checkAgain = true
			break
		}
	}
	fmt.Println(isIn, checkAgain)
}

/* func main() {
	nums1 := []int{4, 5, 6, 7, 0, 1, 2}
	nums2 := []int{2, 5, 6, 0, 0, 1, 2}
	nums3 := []int{1, 2, 3, 4, 5}
	nums4 := []int{1, 1}
	testSearch(nums1, 1)
	testSearch(nums2, 0)
	testSearch(nums3, 5)
	testSearch(nums4, 0)
} */