前言
在有序数组中查找元素的时候，如果是从头到尾遍历一遍查找，它的工夫复杂度是O(N），而通过二分查找，每次查找过滤一半元素，能够优化到O(logn)。
如图所示，low 和 high示意待查找区间的下标，mid 示意待查找区间的两头元素下标，通过管制low、high的地位来放大查找区间的范畴。
1、二分查找
思路
1、mid是low、high的两头节点，每次循环与target目标值比照大小
2、如果mid大于target,则low挪动到mid+1的地位
如果mid小于target,则high挪动到mid-1的地位
如果mid等于target则阐明找到指定的元素，返回后果
3、如果low、high重合了还没找到指定元素，则阐明该元素不存在
留神：
1、终止条件是min <= max，此时min、max重合，查找区间为0
2、mid的取值，用mid=(low+high)/2的话，如果值特地大是可能会溢出的，所以用mid= min + (max-min)/2
func BinarySearch(a []int, v int) int { length := len(a) min := 0 max := length - 1 for min <= max { mid := min + (max-min)/2 if a[mid] == v { return mid } else if a[mid] < v { min = mid + 1 } else if a[mid] > v { max = mid - 1 } } return -1}变体1：查找第一个值等于给定值的元素
思路
查第一个呈现的目标值，就是在查到目标值当前，批改max的地位持续往左查找，直到mid的地位为0了或者mid的右边地位元素不等于目标值了进行。
func BinarySearchFirst(a []int, v int) int { length := len(a) min := 0 max := length - 1 for min <= max { mid := min + (max-min)/2 if a[mid] == v { //如果相邻右边一位不等于搜寻值或者搜寻值为数组第一个元素则返回 if (mid == 0) || (a[mid-1] != v) { return mid } else { max = mid - 1 } } else if a[mid] < v { min = mid + 1 } else if a[mid] > v { max = mid - 1 } } return -1}变体2：查找最初一个值等于给定值的元素
思路
查最初一个呈现的目标值，就是在查到目标值当前，批改min的地位持续往右查找，直到mid的地位为length-1了或者mid的左边地位元素不等于目标值了进行。
func BinarySearchLast(a []int, v int) int { length := len(a) min := 0 max := length - 1 for min <= max { mid := min + (max-min)/2 if a[mid] == v { //如果相邻左边一位不等于搜寻值或者搜寻值为数组最初一个元素则返回 if (mid == length-1) || (a[mid+1] != v) { return mid } else { min = mid + 1 } } else if a[mid] < v { min = mid + 1 } else if a[mid] > v { max = mid - 1 } } return -1}变体3:查找第一个值大于等于给定值的元素
思路
1、如果a[mid] 的值小于target，则min = mid + 1
2、如果a[mid] 的值大于等于target，则需判断这个a[mid] 是不是咱们要找的第一个值大于等于给定值的元素。如果 a[mid] 右边曾经没有元素，或者右边的元素小于要查找的值target，那 a[mid] 就是咱们要找的元素。否则将max更新为mid-1持续往左查找。
func BinarySearchFirstGT(a []int, v int) int { length := len(a) min := 0 max := length - 1 for min <= max { mid := min + (max-min)/2 if a[mid] >= v { //如果相邻右边一位小于搜寻值或者搜寻值为数组第一个元素则返回 if (mid == 0) || (a[mid-1] < v) { return mid } else { max = mid - 1 } } else { min = mid + 1 } } return -1}变体4:查找最初一个小于等于给定值的元素
思路
1、如果a[mid]的值大于target，则max = mid - 1
2、如果a[mid]的值小于等于target，则需判断这个a[mid] 是不是咱们要找的最初一个值小于等于给定值的元素。如果 a[mid] 左边曾经没有元素，或者左边的元素小于要查找的值target，那 a[mid] 就是咱们要找的元素。否则将min更新为mid+1持续往右查找。
func BinarySearchLastLT(a []int, v int) int { length := len(a) min := 0 max := length - 1 for min <= max { mid := min + (max-min)/2 if a[mid] <= v { //如果相邻左边一位大于搜寻值或者搜寻值为数组最初一个元素则返回 if (mid == length-1) || (a[mid+1] > v) { return mid } else { min = mid + 1 } } else if a[mid] > v { max = mid - 1 } } return -1}参考资料：《数据结构与算法之美》