引入

很多时候我们会在使用数组的时候找中间位置

比如常见的算法 二分查找 归并排序 快速排序(某些实现)

我们一拍脑袋写出来的基本都是 (l + r) / 2

其中有几个问题需要我们时刻注意到

区间

我们在写一些算法的时候, 要注意自己写的区间是闭区间还是一个开区间

列如我们定义一个数组a[10] 包含10个int类型的元素数组下标 0-9

在STL中, 很多库函数实现范围的确定都是一个开区间

例如 ve.begin(),ve.end()

假如我们要对一个vector排序的话一般会这样写

如果用开区间去表示一个数组,那么l = 0, r = 10 反之闭区间为 l = 0, r = 9

首先确定区间才能确定我们 (l + r) / 2 表达式求出来的结果是哪一个下标

偶数个元素的数组需要注意

这里直接得出结论

  • 闭区间 (l + r) / 2 的结果为中间偏左边的元素
  • 开区间 (l + r) / 2 的结果为中间偏右边的元素

所以如果要相应的在闭区间和开区间求另外一边的元素的话, 要相应的 +1或者 -1