[算法]二分的常见模板

这两天摸鱼太多，想顺便练习一下算法，找了力扣的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
   }

不愧是源码级别的算法啊，学习一波

注意点

• • 一般来说，使用mid = (high - low) / 2 + low 而不是 mid = (high - low )/2可以防止边界溢出的情况（high很大，low也很大的时候）
  • 注意除于2的幂可以直接使用位运算加速（使用无符号加右移）
  • 注意，l <= r 可以用于最后近似返回，返回时有l==r的情况
  • 二分还可以用于查询区间值，返回当前数据段的右边，即 x ∈ (l, r] ，返回r的下标

注意点二

有一些二分没有给出指定查找元素

对于的 left + 1 ，要么是更大的值（升序），要么突然降序，掉到了最小值。所以无论如何，最小值还是包括在寻找范围内的。而右侧区域，如果草率就 right - 1 的话，可能就会错过最小值了

当 while (left < right) 时，对应的更新式是 left = middle + 1 ， right = middle

当 while (left <= right) 时，对应的更新式是 left = middle + 1，right = middle - 1

本题由于【当区间长度为1时，即可停止二分查找】，所以是 while (left < right) ，所以是 left = middle + 1，right = middle

退出循环 left == right，如果可以确定区间 [left..right] 一定有解，直接返回 left 就可以。否则还需要对 left 这个位置单独做一次判断；

插入位置

即寻找当前输入中左边元素都小于等于这个值，右边元素都大于这个值的位置

func binfind(arr []int, tar int) int {
    l, h := 0, len(arr)-1
    for l < h {
        mid := int(uint(l+h) >> 1)

        if arr[mid] > tar {
            h = mid
        } else {
            l = mid + 1
        }

    }

    return l
}

第二种

func searchInsert(nums []int, target int) int {
   
    low, high := 0, len(nums)-1

    for low <= high {
        if mid := int(uint(low+high) >> 1); nums[mid] == target {
            return mid
        } else {
            if nums[mid] < target {
                low = mid + 1
            } else {
                high = mid - 1
            }
        }
    }

    return low
}