这串长尾词能否用二分法快速定位？
- 内容介绍
- 文章标签
- 相关推荐
本文共计336个文字，预计阅读时间需要2分钟。
首先，我们明确两点，都是由某个可检查的条件决定的，将一个区间分为两半。因此，我们首先定义一个check函数，用于判断区间mid。第二步，对区间进行划分，分为两种情况。
首先我们明确，二分都是由于某个可以检查的条件，将一个区间分为两半
所以我们首先有一个check函数,对中间mid进行判断
func check(mid int) bool {
}
第二步，对区间进行划分
两种区间的划分，对应两种写法
// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
func bsearch_1(l int,r int) int
{
for l < r
{
mid := (l + r )>> 1
if check(mid) {// check()判断mid是否满足性质
r = mid
}
else {
l = mid + 1
}
}
return l
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
func bsearch_2(l int,r int) int
{
for l < r
{
mid := (l + r + 1)>> 1
if check(mid) {// check()判断mid是否满足性质
l = mid
}
else {
r = mid - 1
}
}
return l
}
两种写法除了对于区间缩小的写法不同，还要注意当划分为[l, mid - 1]和[mid, r]时，mid的计算需要加一，因为如果不加一，一种极端情况是r刚好和l会相等，又因为l赋值为mid，结果导致mid永远不变陷入死循环
本文共计336个文字，预计阅读时间需要2分钟。
首先，我们明确两点，都是由某个可检查的条件决定的，将一个区间分为两半。因此，我们首先定义一个check函数，用于判断区间mid。第二步，对区间进行划分，分为两种情况。
首先我们明确，二分都是由于某个可以检查的条件，将一个区间分为两半
所以我们首先有一个check函数,对中间mid进行判断
func check(mid int) bool {
}
第二步，对区间进行划分
两种区间的划分，对应两种写法
// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
func bsearch_1(l int,r int) int
{
for l < r
{
mid := (l + r )>> 1
if check(mid) {// check()判断mid是否满足性质
r = mid
}
else {
l = mid + 1
}
}
return l
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
func bsearch_2(l int,r int) int
{
for l < r
{
mid := (l + r + 1)>> 1
if check(mid) {// check()判断mid是否满足性质
l = mid
}
else {
r = mid - 1
}
}
return l
}
两种写法除了对于区间缩小的写法不同，还要注意当划分为[l, mid - 1]和[mid, r]时，mid的计算需要加一，因为如果不加一，一种极端情况是r刚好和l会相等，又因为l赋值为mid，结果导致mid永远不变陷入死循环