## 二分法查找
>
```go
### 常规写法
func dichotomy(val int, lst []int) int {
//实例三个值, 用于缩小范围,快速查找
//start=0 代表下标为0
//end=len(lst) -1 代表数组最大下标
//mid=初使为0
start, end, mid := 0, len(lst)-1, 0
for {
mid = (start + end) / 2 //求中间下位值, golang整形除取最小值,相当于math.Floor
fmt.Printf("start:%d, end:%d, mid:%d, want: %d \n", start, end, mid, val) //打印
if val > lst[mid] { //如果目标值大于中间值,则将中间mid + 1赋值给start
start = mid + 1
} else if val < lst[mid] { //如果目标值小于中间值,则将中间mid-1赋值给end
end = mid - 1
} else { //表示值相等,找到目标下标
break
}
if start > end { //如果start大于end则跳出,未找到
mid = -1
break
}
}
return mid
}
```
### 推荐写法
```go
func dichotomy(val int, lst []int) int {
//实例三个值, 用于缩小范围,快速查找
//start=0 代表下标为0
//end=len(lst) -1 代表数组最大下标
//mid=初使为0
start, end, mid := 0, len(lst)-1, 0
if val == lst[start] {
return start
}
if val == lst[end-1] {
return end - 1
}
if val > lst[end] || val < lst[start] {
return -1
}
for {
mid = (start + end) / 2 //求中间下位值, golang整形除取最小值,相当于math.Floor
fmt.Printf("start:%d, end:%d, mid:%d, want: %d \n", start, end, mid, val) //打印
if val > lst[mid] { //如果目标值大于中间值,则将中间mid + 1赋值给start
start = mid + 1
} else if val < lst[mid] { //如果目标值小于中间值,则将中间mid-1赋值给end
end = mid - 1
} else { //表示值相等,找到目标下标
break
}
if start > end { //如果start大于end则跳出,未找到
mid = -1
break
}
}
return mid
}
```
#### test demo
```go
func TestDichotomy(t *testing.T) {
fmt.Println("第3种")
lst := []int{
1, 2, 3, 4, 5, 6,
}
sort.Ints(lst)
fmt.Println("排完序的切片:", lst)
tests := []struct {
name string
val int
want int
}{
{
name: "测试1",
val: 3,
want: 2,
},
{
name: "测试2",
val: 18,
want: -1,
},
{
name: "测试3",
val: 6,
want: 5,
},
{
name: "测试4",
val: 1,
want: 0,
},
{
name: "测试5",
val: -100,
want: -1,
},
}
for _, item := range tests {
t.Run(item.name, func(t *testing.T) {
_val := dichotomy(item.val, lst)
if _val != item.want {
t.Errorf("want:%d, wantErr:%d", item.want, _val)
}
})
}
}
```
GITHUB https://github.com/yezihack/math/tree/master/dichotomy
有疑问加站长微信联系（非本文作者）
