位置: IT常识 - 正文
前缀和与对数器与二分法(对数前面有符号怎么计算)
编辑：rootadmin推荐整理分享前缀和与对数器与二分法(对数前面有符号怎么计算)，希望有所帮助，仅作参考，欢迎阅读内容。
文章相关热门搜索词:前缀运算符,前缀计算法,对数前面有符号怎么计算,前缀求值,前缀算式的值怎么算,前缀匹配算法,对数前面有符号怎么计算,前缀求值,内容如对您有帮助，希望把文章链接给更多的朋友！
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就是局部最小，这里我们也成功使用了二分法。
代码实现：
