golang 实现二分法查找(无bug版本)

## 二分法查找 > ```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