前缀求和（前缀和与对数器与二分法）
1. 前缀和
假设有一个数组 ，我们想大量频繁的去访问L到R这个区间的和 ，我们该怎么快速的得出 。
如果我们每次都遍历一遍累加这样就太慢了 。我们可以开辟一个数组 ，把每个位置的和加在一起存进去 。
如果我们要找的L到R中 ，L是0 。那么[L ，R]的和就为H[R] ，如果L不为0 ，那么[L ，R]的和就为H[R]-H[L-1] 。这样我们找前缀和就会快很多 。代码实现如下：
2. 对数器
假设我们有一个函数f1是生成1-5的随机数 ，我们怎么用它去设置1-7的随机数函数
？
第一步：将这个1-5的随机数改成只有0 ，1对数器。
这里的意思是：如果是1和2那么就设置成0 ，如果是4和5就设置成1 ，如果是3就重新生成 。第二步：用0 ，1对数器改造一个0-7的随机函数
。
我们调用三次f2 ，然后移位就能拥有000-111的一个取值范围 。第三步：用0-7的随机函数 ，对构造一个1-7的生成器
。
我们也可以验证一下：
3. 二分查找
二分有两种写法 ，一种是右边是闭区间 ，一种是右边是开区间 。这两种的写法也是有一些差别的 。
首先 ，说一下右边是闭区间：
如果右边是闭区间 ，那么right的下标就是n-1 。
如果我们想查找8这个数 ，我们先算出第一个中间位置left+((right-left)>>1) ，这个等同于(left+right)/2 。所以mid=5 ，下标5的数比8小 ，我们就left=mid+1 ，往后走一步 。
我们再继续算mid=8 ，下标为8的数据是6比8小 ，mid继续+1 。
继续算mid=10 ，下标10的数据是9比8大 ，所以让right=mid-1 。
此时 ，left和right相等 ，继续查找 。mid=9 ，下标9的数据是8 ，就查找到了 。代码实现： 右边是开区间：
如果右边是开区间 ，那么right就是n 。
如果我们想要查找3 ，那么mid=(0+12)/2就是6 ，下标为6的数据是4 ，比3大 ，因为右边是开区间 ，如果我们还是right=mid-1 ，那么right就是5 ，5是开区间 ，就找不到3了 。所以我们要让right=mid 。
然后继续算mid=(0+6)/2 ，就为3 。下标3的数是2比3小 ，就让left=mid+1 。
继续算mid=(4+6)/2 ，就为5 ，下标为5的数据是3就找到了 。
这里的循环条件是left<right就继续找 ，如果left==right就结束 ，因为是左闭右开 ，假设[5 ，5)就已经没有数据可以取了 。代码实现：
3.1 二分的变形
3.1.1 第一种变形
在一个有序数组中 ，找>=某个数最左侧的位置
。
如果我们要找>=3的最左侧的数 ，我们该怎么找呢？先找出mid=(0+10)/2 ，为5 ，下标为5的数据是4>=3 ，所以我们用index记录下标4 。然后继续right=mid-1 ，继续二分 。
mid=(0+4)/2 ，为2 ，下标为2的数据是2<3 ，index不变 ，让left=mid+1 。
继续二分 ，mid=(3+4)/2 ，为3 ，下标为3的数是3>=3 ，将index改成3 。然后让right=mid-1 。
这样left和right都到下标3的位置 ，在继续二分一遍 ，下标还是3 ，让right=mid-1 。然后left>right ，循环结束 。代码实现：
找<=right的最右侧也是相同的道理：
3.1.2 第二种变形
我们要知道 ，有序一定二分 ，但不在有序的情况下 ，我们有时候也可以使用二分 。
局部最小值问题：在一个无序数组里 ，正数 ，负数 ，0都可能存在 ，但是相邻的两个数一定不相等 。然后给我返回一个局部最小的位置。
第一种情况：如果下标0位置上的数小于1位置上的数 ，就叫做局部最小 。
第二种情况：如果下标N-1位置上的数小于N-2位置上的数 ，就叫做局部最小 。
第三种情况：中间位置上的数 ，既要比左边小 ，也要比右边小 ，才叫局部最小 。思路：
如果前两种情况都不满足 ，说明它是这样的一共情况：
中间是相邻两个不相等的 ，所以中间一定有局部最小 。我们先求出mid 。
如果mid比mid-1的数据大 。
说明左边一定存在局部最小 ，右边就不看了 ，直接去左边找 。如果mid比mid+1的数据大 。
说明右边一定存在局部最小 ，左边就可以不看了 。当mid不比左变大也不比右边大 ，说明mid就是局部最小 ，这里我们也成功使用了二分法 。
代码实现：
创心域SEO版权声明：以上内容作者已申请原创保护，未经允许不得转载，侵权必究！授权事宜、对本内容有异议或投诉，敬请联系网站管理员，我们将尽快回复您，谢谢合作！