import "fmt"
func checkIfExist(arr []int) bool {
    found := false
    sort(arr, 0, len(arr) - 1)
    fmt.Println(arr)
    for i, num := range arr{
        
        if num % 2 == 0{
            fmt.Println(num, num/2)
            fmt.Println(binarySearch(arr, num / 2, 0, len(arr) - 1))
            if idx, ok := binarySearch(arr, num / 2, 0, len(arr) - 1); ok{
                if idx != i{
                found = true
                break
                }
            }
        }
    }
    
    return found
}

func partition(nums []int, low int, high int) int {
    pivot := nums[high]
    i := low - 1
    
    for j := low; j <= high - 1; j++ {
        if nums[j] < pivot{
            i = i + 1
            nums[i], nums[j] = nums[j], nums[i]
        }
    }
    
    nums[i+1], nums[high] = nums[high], nums[i+1]
    return i+1
}

func sort(nums []int, low int, high int){
    
    if low < high{
        loc := partition(nums, low, high)
        sort(nums, low, loc-1)
        sort(nums, loc+1, high)
    }
    
}

func binarySearch(arr []int, num int, low int, high int) (index int, found bool) {
    
    if low <= high{
    
    mid := int((low + high) / 2)
    
    if arr[mid] == num{
        index = mid
        found = true
    } else if arr[mid] < num{
        index, found = binarySearch(arr, num, mid + 1, high)
    } else if arr[mid] > num{
        index, found = binarySearch(arr, num, low, mid - 1)
    } else {
        index = -1
        found = false
    }
    
    } else {
        index = -1
        found = false
    }
    return index, found
    
}