二分法模板
摘要
- 二分法的基本原理
- 通用模板
- 什么时候死循环
- 为什么能做到通用
- 使用二分法解决求第一个位置，求最后一个位置和求任意位置的二分问题
- 二分算法的判断条件
基本原理
- start, end
- mid
target = 11
01 03 04 05 06 10 11 14 15 17
0 1 2 3 4 5 6 7 8 9
0 9 mid=4
5 9 mid=7
5 6 mid=5
6
通用模板
死循环的案例
- nums = [1, 1], target = 1
- nums = [1, 2], target = 1
- mid 操作有可能偏左或者偏右
写出不会死循环的二分法
- start + 1 < end
- start + (end - start) / 2
- A[mid] ==, <, >
- A[start] A[end] ? Target
func BinarySearch(nums []int, target int) int {
start, end := 0, len(nums) - 1
for start+1 < end {
mid := start + (end-start)/2
if nums[mid] == target {
end = mid
} else if nums[mid] < target {
start = mid
} else {
end = mid
}
}
if nums[start] == target {
return start
}
if nums[end] == target {
return end
}
return -1
}
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。