package main

import(
	"fmt"
	"math/rand"
	"sort"
)
type ElemType struct{
	data int
}
type ElemTypeSlice []ElemType
func (p ElemTypeSlice) Less(i,j int)bool{
	if p[i].data<p[j].data{
		return true
	}
	return false
}
func (p ElemTypeSlice) Len()int{
	return len(p)
}
func (p ElemTypeSlice) Swap(i,j int){
	p[i],p[j]=p[j],p[i]
}
func SearchExchangeInsert(A []ElemType , x ElemType){
	lens:=len(A)
	low,high,mid:=0,lens-1,0
	for low<=high{
		mid=(low+high)/2
		if(A[mid]==x){
			break
		}else if A[mid].data<x.data{
			low=mid+1
		}else{
			high=mid-1
		}
	}
	if A[mid]==x&&mid!=lens-1{//交换x与其后面的值
		var temp ElemType
		temp=A[mid]
		A[mid]=A[mid+1]
		A[mid+1]=temp
	}

	

	if low>high{//查找失败
		//向后移动一个元素
		// 这个为切片操作

		// t:=A[:mid+1]
		// f:=A[mid+1:]
		// t=append(t,x)
		// t=append(t,f...)
		// A=t
		// fmt.Println(t)

		// 这个为数组操作
		A=append(A,A[lens-1])

		for i:=lens-1;i>mid+1;i--{

			A[i]=A[i-1]
		}
		A[mid+1]=x
		fmt.Println(A)

	}
}
func main()  {
	// var a [4]int=[4]int{1,2,3,4}
	// a:=[4]int{2,3,4,5}
	// a:=[...]int{1,2,3,4,5}

	var a ElemTypeSlice
	for i:=0;i<10;i++{
		var e ElemType=ElemType{
			data:rand.Intn(100),
		}
		a=append(a,e)
	}
	var b ElemType=ElemType{
		data:rand.Intn(100),
		// data:81,
	}
	sort.Sort(a)
	s:=a[:]
	fmt.Println(b)
	fmt.Println(s)
	SearchExchangeInsert(s,b)
	fmt.Println(s)
}