共计 2163 个字符，预计需要花费 6 分钟才能阅读完成。
前言
在有序数组中查找元素的时候，如果是从头到尾遍历一遍查找，它的工夫复杂度是 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
}参考资料：《数据结构与算法之美》