[算法]二分的常见模板

这两天摸鱼太多,想顺便练习一下算法,找了力扣的14天系列,准备系统地刷一刷

第一天是二分,二分想法还是挺简单,主要是边界需要处理一下,一般一些常见的题无脑套模板就行

总的来说看过两个主流模板,主要区别是在边界的处理问题上

go语言为数不对地也自带了一个二分查找的api,顺带看一下go语言源码的实现,果然就是超过50%与超过99%的区别啊

模板一

func search(nums []int, target int) int {

	var low, high = 0, len(nums) - 1

	for low <= high {
		var mid = (high-low)/2 + low
		if nums[mid] == target {
			return mid
		}
		if nums[mid] > target {
			high = mid - 1
		} else {
			low = mid + 1
		}
	}
	return -1
}

模板二,go语言自带

func Search(n int, f func(int) bool) int {
	// Define f(-1) == false and f(n) == true.
	// Invariant: f(i-1) == false, f(j) == true.
	i, j := 0, n
	for i < j {
		h := int(uint(i+j) >> 1) // avoid overflow when computing h
		// i ≤ h < j
		if !f(h) {
			i = h + 1 // preserves f(i-1) == false
		} else {
			j = h // preserves f(j) == true
		}
	}
	// i == j, f(i-1) == false, and f(j) (= f(i)) == true  =>  answer is i.
	return i
}

不愧是源码级别的算法啊,学习一波 :huaji22:

注意点

  • 一般来说,使用mid = (high - low) / 2 + low 而不是 mid = (high - low )/2可以防止边界溢出的情况(high很大,low也很大的时候)
  • 注意除于2的幂可以直接使用位运算加速(使用无符号加右移)
  • 点赞

    发表评论

    电子邮件地址不会被公开。必填项已用 * 标注