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