# 二分查找法（Golang版本）

2017/05/08 10:10

``````package main

import (
"fmt"
"math"
)

type DataStruct struct {
Data []int
}

func main() {
a1 := DataStruct{[]int{1, 2, 5, 7, 15, 25, 30, 36, 39, 51, 67, 78, 80, 82, 85, 91, 92, 97}}

fmt.Println(a1)
}``````

1. left = 1, right = 18; mid = (1+18)/2 = 9;   51 > 30

2. left = 1, right = mid - 1 = 8; mid = (1+8)/2 = 4;   15 < 30

3. left = mid + 1 = 5, right = 8; mid = (5+8)/2  = 6;  30 = 30 查找完毕

``````func (d *DataStruct) Find(k int) int {
left, right, mid := 1, len(d.Data), 0
for {
// mid向下取整
mid = int(math.Floor(float64((left + right) / 2)))
if d.Data[mid] > k {
// 如果当前元素大于k，那么把right指针移到mid - 1的位置
right = mid - 1
} else if d.Data[mid] < k {
// 如果当前元素小于k，那么把left指针移到mid + 1的位置
left = mid + 1
} else {
// 否则就是相等了，退出循环
break
}
// 判断如果left大于right，那么这个元素是不存在的。返回-1并且退出循环
if left > right {
mid = -1
break
}
}
// 输入元素的下标
return mid
}``````

``````func main() {
a1 := DataStruct{[]int{1, 2, 5, 7, 15, 25, 30, 36, 39, 51, 67, 78, 80, 82, 85, 91, 92, 97}}

fmt.Println(a1.Find(30)) //打印 6
}``````

0
0 收藏

0 评论
0 收藏
0