go语言整数二分模板

本文主要是介绍go语言整数二分模板，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

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

这篇关于go语言整数二分模板的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！