[算法]二分的常见模板

这两天摸鱼太多,想顺便练习一下算法,找了力扣的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的幂可以直接使用位运算加速(使用无符号加右移)
    • 注意,l <= r 可以用于最后近似返回,返回时有l==r的情况
    • 二分还可以用于查询区间值,返回当前数据段的右边,即 x ∈ (l, r] ,返回r的下标
点赞

发表评论

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