type binarySearch struct {
keys []byte
values []int
}
func (this *binarySearch)put(key byte,value int){
index,isFind :=this.rank(key)
if isFind{
this.values[index] = value
return
}
rear:=append([]byte{},this.keys[index:]...)
rear2:=append([]int{},this.values[index:]...)
this.keys = append(append(this.keys[:index],key),rear...)
this.values = append(append(this.values[:index],value),rear2...)
return
}
func (this *binarySearch)get(key byte)(int,bool){
index,isFind :=this.rank(key)
if !isFind{
return 0,false
}
return this.values[index],true
}
func (this *binarySearch)rank(key byte)(int,bool){
if len(this.keys) == 0{
return 0,false
}
start := 0
end := len(this.keys)-1
for{
if start==end{
if key == this.keys[(start+end)/2]{
return start,true
}
return start+1,false
}
if key > this.keys[(start+end)/2]{
start = (start+end)/2+1
}else if key < this.keys[(start+end)/2]{
end = (start+end)/2-1
}else{
return (start+end)/2,true
}
}
return start,false
}
func main(){
var BSST binarySearch
BSST.put('a',15)
//fmt.Println(BSST.keys)
BSST.put('b',17)
BSST.put('c',17)
BSST.put('d',19)
BSST.put('w',21)
BSST.put('c',19)
fmt.Println(BSST.get('g'))
fmt.Println(BSST.get('c'))
fmt.Println(BSST.keys)
fmt.Println(BSST.values)
}
二分查找 golang
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 查找概念 查找(Searching)： 即根据给定的某个值，在查找表中确定一个其关键字给定值的数据元素(或记录)。...
- 数据结构与算法--查找之顺序查找和二分查找 符号表的目的是将一个键和一个值关联起来，可以将一对键值对插入到符号表中...
- 二分查找二分查找 又称折半查找，要求数组必须是有序的数列，是一种有序查找算法。二分查找的时间复杂度是O(log n...
