Go高并发实战3.6. 二分法查找算法
不要小瞧了二分法查找算法，在接下来的的一致性hash算法实现过程中会用到它！利用他去hash环上根据传入的key的hash值找对应服务器的ip地址从而实现负载均衡器功能！nginx自带的负载均衡我们通过golang手写一个很轻松！
什么叫做二分法查找算法？
二分查找的基本思想是通过不断缩小查找的范围，每次将数据与数组中间的数据进行比较，从而一步一步进行比较并且缩小范围，进而找到目标数。
二分法查找，是在已经排好序的序列中，定义一个起始位置start(即序列第一个元素)和一个终止位置end(即序列最后一个元素),通过mid=(start+end)/2计算出中间位置，通过待查找元素与mid中间位置的元素进行比较，如果待查找元素比中间位置mid对应的值小，那么将end = mid -1(即将end结束位置移动到mid中间左边一个位置),如果比中间对应的值大，那么将start = mid + 1 (即将start的位置移动到mid右边一个位置)，一直循环查找，直到start > end,证明没找到对应的元素，停止循环。
看文字你是看不懂的，上代码：
待查找有序数组序列：1, 2, 3, 4, 5, 6, 7
A：
定义
start = 0 ,
end = 6,
mid = (start + end ) / 2 = (0 + 6) / 2 = 3,
arr[mid] = arr[3] = 4
B：
假设需要查找”2”,
因为
2 < arr[mid] = arr[3] = 4;
所以需要将end移动到mid左边一个位置，
即end = mid - 1 = 3 - 1 = 2,
此时重新计算
mid = (start +end ) / 2 = (0 + 2) / 2 = 1;
arr[mid] = arr[1] = 2 ,
继续将 2与arr[mid] = arr[1] = 2进行比较，
发现相等，成功找到数字”2”所在的位置。
待查找有序数组序列：1, 2, 3, 4, 5, 6, 7
A：
假设需要查找”7”，
因为 7 > arr[mid] = arr[3] = 4,
所以需要将start移动到mid右边一个位置，
即start = mid + 1 = 4,
此时重新计算
mid = (start +end) / 2 = (4+ 6)/2 = 5,
arr[mid] = arr[5] = 6,
因为7>arr[mid] = arr[5] = 6,
所以还是需要将start移动到mid右边一个位置，
即start = mid + 1 = 5 + 1 = 6,
此时重新计算mid = (start +end) / 2 = (6 + 6) / 2 = 6.arr[6] = 7,
此时arr[mid] = arr[6] = 7,
刚好等于待查找数字7，说明成功找到数字”7”所在的位置.
golang当中如何使用二分法查找算法呢？
func hashKey(key string) {
data := []int{10, 22, 11, 22, 17, 26}
fmt.Println(len(data))
i := sort.Search(len(data), func(i int) bool {
return data[i] > 23
})
fmt.Println("最终的结果为", i)
}过程讲解：初始查找的区间是[0,len(data)] 0-6 (0+6)/2 = 3 data[3] = 22 23>22 则 3+1=4 （4+6）/2=5 data[5] = 26 26>23满足条件 那就是5喽
关于 LearnKu
粤公网安备 44030502004330号
推荐文章：