Go猜想录
大道至简,悟者天成
二分法模板

摘要

  • 二分法的基本原理
  • 通用模板
    • 什么时候死循环
    • 为什么能做到通用
  • 使用二分法解决求第一个位置,求最后一个位置和求任意位置的二分问题
  • 二分算法的判断条件

基本原理

  1. start, end
  2. 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 国际许可协议进行许可。