电脑基础 · 2023年3月26日

前缀和与对数器与二分法

前缀和与对数器与二分法

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就是局部最小,这里我们也成功使用了二分法。

代码实现:
前缀和与对数器与二分法