算法

背景

分治算法是一种比较常用的算法思想，通过“分而治之”的思想将大问题化解为小问题并逐个击破，最后将结果合并返回即可。

问题

通过二分查找的方式快速找到数组中的一个值

代码

二分查找算是一个比较特殊的分治法，通过选定有序数组的中间值与目标值比较大小，然后选定中间值的左侧或者右侧(目标值所在区域)继续分治，另一半则直接舍弃。

// 二分查找，根据查得的值大小，排除一半的数组值
// 二分查找是通过双指针的形式来分治的
// 二分查找数组必须有序，否则不叫二分查找
func BinarySearch(target int, arr []int) (index int) {
	left := 0
	right := len(arr) - 1

	for left <= right {
		mid := left + (right-left)/2
		midVal := arr[mid]
		if target == midVal {
			index = mid
			return
		}
		if target > midVal {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}
	return -1
}