Go语言中如何实现整数二分查找算法？

本文共计429个文字，预计阅读时间需要2分钟。

首先，我们明确两点，二分都是基于某个可检查的条件，将一个区间分为两半。因此，我们首先需要一个check函数，用于判断区间mid是否满足条件。函数定义如下：

cbool check(int mid) { // 实现具体的检查逻辑}

第二步，对区间进行划分。有两种划分方式：

1. 如果check(mid)为真，则新的区间为[l, mid-1]。

2.如果check(mid)为假，则新的区间为[mid+1, r]。

这样，我们就可以通过不断缩小区间来找到满足条件的解。

首先我们明确，二分都是由于某个可以检查的条件，将一个区间分为两半
所以我们首先有一个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永远不变陷入死循环