二分查找的应用 ——李江贝， 郝琰 2017年9月28日.

Presentation on theme: "二分查找的应用 ——李江贝， 郝琰 2017年9月28日."— Presentation transcript:

1 二分查找的应用 ——李江贝， 郝琰 2017年9月28日

2 高中学过的二分法

3 查找图解

4 二分法基本思想： 适用范围： 1.题目答案满足某种意义上的单调 性 2.直接求解难以接受 3.验证解是否可行较为容易

5 二分法基本思想： 常见的模型 1.求xx的最值 2.求最少/多需要多少xx才能满足 xx”

6 常见的模型 1.求xx的最值 2.求最少/多需要多少xx才能满足xx” 3.xx最大值尽可能小，xx最小值尽可能大 时间复杂度 log
二分法基本思想： 常见的模型 1.求xx的最值 2.求最少/多需要多少xx才能满足xx” 3.xx最大值尽可能小，xx最小值尽可能大 时间复杂度 log

7 例:一元三次方程求解 题目描述 有形如：ax3+bx2+cx+d=0 这样的一个一元三次方程。给 出该方程中各项的系数(a，b，c，d 均为实数)，并约定 该方程存在三个不同实根(根的范围在-100至100之间)， 且根与根之差的绝对值>=1。要求由小到大依次在同一行 输出这三个实根(根与根之间留有空格)，并精确到小数点 后2位。 输入格式：一行，4个实数a，b，c，d。 输出格式：一行，三个实根，并精确到小数点后2位。

8 算法思路： 1.取一定包含根的某一区间(a,b)，其中 f(a)*f(b)<0
2.取(a,b)的中点c.若f(a)*f(c)<0，则将求解区 间调整为(a,c)；否则，求解区间为(c,b) 3.对新的求解区间重复1,2两操作，直到求解 区间满足题目所要求的的精度为止

9 参考代码： double caculate(double l,double r){ double m;
while(r-l >= 0.001){ //误差范围内 m = (l+r)/2; double mid = f(m),fl = f(l),fr = f(r); if(mid * fl > 0)l = m; //（l,m）中有零点 else if(mid * fr > 0)r = m; //（m,r）中有零点 if(mid == 0)return m; } return m; //当没找到确切的零点时，返回近似值

10 还想了些什么 三次方程求根公式？ 通过求导得到三次函数的两个最值点，然后对三个区间进行二分。

11 OJ 奔跑吧保祥 Description 保祥最近开始使用一款APP进行跑步。 APP中预设了不同的跑步 路径供保祥选择，每一种路径中会自动生成不同的感应位点。 保祥是个不喜欢拐弯抹角的人，因此他选择沿着笔直的宣怀大道 跑步，APP为他规定了跑步的起点和终点。在起点和终点之间,有 N 个位点(不含起点和终点)。跑步时，保祥必须按次序经过每一 个位点，最终到达终点。 为了减少中途找点的次数，提高跑步质量，APP设计者计划删除 一些位点，使得路径中相邻两个位点间的最短距离尽可能长。设 计者计划至多从起点和终点之间删除 M 个位点（不能删除起点 和终点)。求最短距离的最大值。

12 去掉若干个点 求最短距离的最大值

13 算法思路 “最短距离的最大值”，直接求解不方便，但要验证某一值x是否可能 是最短距离比较容易。譬如对于给定的距离值x，只需验证，删除M 个位点后，能否满足各位点间距离均大于等于x即可。因此题目可 转化为求得满足该条件的最大的x。（由于可验证比这个值更大的 距离都不可能是最短距离，而这个距离有可能是最短距离，因此该 值一定是最短距离的最大值）

14 算法思路 “最短距离的最大值”，直接求解不方便，但要验证某一值x是否可能 是最短距离比较容易。譬如对于给定的距离值x，只需验证，删除M 个位点后，能否满足各位点间距离均大于等于x即可。因此题目可 转化为求得满足该条件的最大的x。（由于可验证比这个值更大的 距离都不可能是最短距离，而这个距离有可能是最短距离，因此该 值一定是最短距离的最大值） 从最短距离的最大值x下手。若x=0，各位点间间距一定都大于等于 x（注意，这里的最短距离不一定是真实可达到的最短距离，但它 一定小于等于可达到的最短距离。我们会在计算中逐渐取到可达到 的最短距离的最大值。）因此设low=0,high=L。

15 算法思路 “最短距离的最大值”，直接求解不方便，但要验证某一值x是否可能 是最短距离比较容易。譬如对于给定的距离值x，只需验证，删除M 个位点后，能否满足各位点间距离均大于等于x即可。因此题目可 转化为求得满足该条件的最大的x。（由于可验证比这个值更大的 距离都不可能是最短距离，而这个距离有可能是最短距离，因此该 值一定是最短距离的最大值） 从最短距离的最大值x下手。若x=0，各位点间间距一定都大于等于 x（注意，这里的最短距离不一定是真实可达到的最短距离，但它 一定小于等于可达到的最短距离。我们会在计算中逐渐取到可达到 的最短距离的最大值。）因此设low=0,high=L。 二分区间，令mid=(low+high)/2。讨论，从N个位点中删除M个能 否满足剩余所有位点的间距不比mid 小。若满足，讨论(mid， high),否则，讨论(low，mid)

16 算法思路 注：判断x是否合乎题意的方法：设初始位点的分布存在数组 a[maxn]中。首先，从离起点距离s=0开始，若a[0]<s+x，说明0 到a[0]之间的距离小于这个最短距离，需要把a[0]位点去除，去 除的位点数加一。之后再看0到a[1]，如果还是小于x，去除的 位点数加一，直到找到某一位点离起点距离大于x，把该位点置 为起点，重复上述过程；若a[0]>=s+x，直接把第一个位点置为 起点。以此类推。

17 参考代码 high = L; low = 0; while (high - low > 1) { mid = (high + low) / 2; if (valid(mid, N, M)) low = mid; else high = mid; } if (valid(high, N, M)) cout << high; else cout << low; bool valid(int x, int N, int M) { int start, num=0,j; start = 0; for (j = 0; j <= N - 1; j++) { if (a[j] < start + x) num += 1; else start = a[j]; } return num <= M;

18 OJ 1581 LIS (longest increasing subsequence)
Description 给一个序列，求它的最长递增子序列的长度。 如 这些数字中，1 2 5(4) 7 是最长的上升子序列，长度为4. Input Format 第一行有三个整数n ，代表序列的长度。 接下来一行 n 个正整数代表序列x[1], x[2]……, x[n]。 Output Format 输出最长递增子序列的长度。 注意：答案没有对任何数取模。

19 一个共识 如果一个序列为1， 3， 5， 9， 6， 8 我们先只考虑前5个元素，（1，3，5，9，6） 可以构 成两个最长递增子序列（1，3，5，9）和（1，3，5， 6） 这时我们考虑元素8，他更喜欢（1，3，5，6）这个序 列，而讨厌（1，3，5，9）这个序列，因为它可以与 1，3，5，6构成长度为5的序列

20 我们怎么办呢 开一个数组d[] d[i] 存储 长度为i的最长递增子序列 的 最小末尾

21 算法思路 以序列{6，7，8，9，10，1，2，3，4，5，6}来说明

22 算法思路 以序列{6，7，8，9，10，1，2，3，4，5，6}来说明
程序开始时，最长递增序列长度为1（每个元素都是一个长 度为1的递增序列），当处理第2个元素时发现7比最长递增 序列6的最大元素还要大，所以将6，7结合生成长度为2的递 增序列，说明已经发现了长度为2的递增序列，依次处理， 到第5个元素(10)，这一过程中B数组的变化过程是

23 算法思路 以序列{6，7，8，9，10，1，2，3，4，5，6}来说明
程序开始时，最长递增序列长度为1（每个元素都是一个长 度为1的递增序列），当处理第2个元素时发现7比最长递增 序列6的最大元素还要大，所以将6，7结合生成长度为2的递 增序列，说明已经发现了长度为2的递增序列，依次处理， 到第5个元素(10)，这一过程中B数组的变化过程是 6

24 算法思路 以序列{6，7，8，9，10，1，2，3，4，5，6}来说明
程序开始时，最长递增序列长度为1（每个元素都是一个长 度为1的递增序列），当处理第2个元素时发现7比最长递增 序列6的最大元素还要大，所以将6，7结合生成长度为2的递 增序列，说明已经发现了长度为2的递增序列，依次处理， 到第5个元素(10)，这一过程中B数组的变化过程是 6  6，7

25 算法思路 以序列{6，7，8，9，10，1，2，3，4，5，6}来说明
程序开始时，最长递增序列长度为1（每个元素都是一个长 度为1的递增序列），当处理第2个元素时发现7比最长递增 序列6的最大元素还要大，所以将6，7结合生成长度为2的递 增序列，说明已经发现了长度为2的递增序列，依次处理， 到第5个元素(10)，这一过程中B数组的变化过程是 6  6，7  6，7，8

26 算法思路 以序列{6，7，8，9，10，1，2，3，4，5，6}来说明
程序开始时，最长递增序列长度为1（每个元素都是一个长 度为1的递增序列），当处理第2个元素时发现7比最长递增 序列6的最大元素还要大，所以将6，7结合生成长度为2的递 增序列，说明已经发现了长度为2的递增序列，依次处理， 到第5个元素(10)，这一过程中B数组的变化过程是 6  6，7  6，7，8  6，7，8，9

27 算法思路 以序列{6，7，8，9，10，1，2，3，4，5，6}来说明
程序开始时，最长递增序列长度为1（每个元素都是一个长 度为1的递增序列），当处理第2个元素时发现7比最长递增 序列6的最大元素还要大，所以将6，7结合生成长度为2的递 增序列，说明已经发现了长度为2的递增序列，依次处理， 到第5个元素(10)，这一过程中B数组的变化过程是 6  6，7  6，7，8  6，7，8，9 6，7，8，9，10

28 算法思路 以序列{6，7，8，9，10，1，2，3，4，5，6}来说明   之前处理到过的序列: 6，7，8，9，10

29 算法思路 以序列{6，7，8，9，10，1，2，3，4，5，6}来说明 之前处理到过的序列: 6，7，8，9，10
  之前处理到过的序列: 6，7，8，9，10 开始处理第6个元素是1，查找比1大的最小元素，发现是长度为1的子序列的最大元素6， 说明1是最大元素更小的长度为1的递增序列，用1替换6，形成新数组1，7，8，9，10。 然后查找比第7个元素(2)大的最小元素，发现7，说明存在长度为2的序列，其末元素2， 比7更小，用2替换7，依次执行，直到所有元素处理完毕，生成新的数组1，2，3，4， 5，最后将6加入B数组，形成长度为6的最长递增子序列.

30 算法思路 以序列{6，7，8，9，10，1，2，3，4，5，6}来说明 之前处理到过的序列: 6，7，8，9，10
  之前处理到过的序列: 6，7，8，9，10 开始处理第6个元素是1，查找比1大的最小元素，发现是长度为1的子序列的最大元素6， 说明1是最大元素更小的长度为1的递增序列，用1替换6，形成新数组1，7，8，9，10。 然后查找比第7个元素(2)大的最小元素，发现7，说明存在长度为2的序列，其末元素2， 比7更小，用2替换7，依次执行，直到所有元素处理完毕，生成新的数组1，2，3，4， 5，最后将6加入B数组，形成长度为6的最长递增子序列. 1，7，8，9，10

31 算法思路 以序列{6，7，8，9，10，1，2，3，4，5，6}来说明 之前处理到过的序列: 6，7，8，9，10
  之前处理到过的序列: 6，7，8，9，10 开始处理第6个元素是1，查找比1大的最小元素，发现是长度为1的子序列的最大元素6， 说明1是最大元素更小的长度为1的递增序列，用1替换6，形成新数组1，7，8，9，10。 然后查找比第7个元素(2)大的最小元素，发现7，说明存在长度为2的序列，其末元素2， 比7更小，用2替换7，依次执行，直到所有元素处理完毕，生成新的数组1，2，3，4， 5，最后将6加入B数组，形成长度为6的最长递增子序列. 1，7，8，9，10  1，2，8，9，10

32 算法思路 以序列{6，7，8，9，10，1，2，3，4，5，6}来说明 之前处理到过的序列: 6，7，8，9，10
  之前处理到过的序列: 6，7，8，9，10 开始处理第6个元素是1，查找比1大的最小元素，发现是长度为1的子序列的最大元素6， 说明1是最大元素更小的长度为1的递增序列，用1替换6，形成新数组1，7，8，9，10。 然后查找比第7个元素(2)大的最小元素，发现7，说明存在长度为2的序列，其末元素2， 比7更小，用2替换7，依次执行，直到所有元素处理完毕，生成新的数组1，2，3，4， 5，最后将6加入B数组，形成长度为6的最长递增子序列. 1，7，8，9，10  1，2，8，9，10 1，2，3，9，10

33 算法思路 以序列{6，7，8，9，10，1，2，3，4，5，6}来说明 之前处理到过的序列: 6，7，8，9，10
  之前处理到过的序列: 6，7，8，9，10 开始处理第6个元素是1，查找比1大的最小元素，发现是长度为1的子序列的最大元素6， 说明1是最大元素更小的长度为1的递增序列，用1替换6，形成新数组1，7，8，9，10。 然后查找比第7个元素(2)大的最小元素，发现7，说明存在长度为2的序列，其末元素2， 比7更小，用2替换7，依次执行，直到所有元素处理完毕，生成新的数组1，2，3，4， 5，最后将6加入B数组，形成长度为6的最长递增子序列. 1，7，8，9，10  1，2，8，9，10 1，2，3，9，10 1，2，3，4，10

34 算法思路 以序列{6，7，8，9，10，1，2，3，4，5，6}来说明 之前处理到过的序列: 6，7，8，9，10
  之前处理到过的序列: 6，7，8，9，10 开始处理第6个元素是1，查找比1大的最小元素，发现是长度为1的子序列的最大元素6， 说明1是最大元素更小的长度为1的递增序列，用1替换6，形成新数组1，7，8，9，10。 然后查找比第7个元素(2)大的最小元素，发现7，说明存在长度为2的序列，其末元素2， 比7更小，用2替换7，依次执行，直到所有元素处理完毕，生成新的数组1，2，3，4， 5，最后将6加入B数组，形成长度为6的最长递增子序列. 1，7，8，9，10  1，2，8，9，10 1，2，3，9，10 1，2，3，4，10  1，2，3，4，5

35 算法思路 以序列{6，7，8，9，10，1，2，3，4，5，6}来说明 之前处理到过的序列: 6，7，8，9，10
  之前处理到过的序列: 6，7，8，9，10 开始处理第6个元素是1，查找比1大的最小元素，发现是长度为1的子序列的最大元素6， 说明1是最大元素更小的长度为1的递增序列，用1替换6，形成新数组1，7，8，9，10。 然后查找比第7个元素(2)大的最小元素，发现7，说明存在长度为2的序列，其末元素2， 比7更小，用2替换7，依次执行，直到所有元素处理完毕，生成新的数组1，2，3，4， 5，最后将6加入B数组，形成长度为6的最长递增子序列. 1，7，8，9，10  1，2，8，9，10 1，2，3，9，10 1，2，3，4，10  1，2，3，4，5  1，2，3，4，5，6

36 算法思路 而在上述过程中，为了查找到合适的放置元素的位置，我们 需要用到二分查找
二分查找的结果，我们的目的是找到这样的一个j，使满足 A[B[j]] > A[i]的所有j中，j取得最小值

37 算法思路 而在上述过程中，为了查找到合适的放置元素的位置，我们 需要用到二分查找
二分查找的结果，我们的目的是找到这样的一个j，使满足 A[B[j]] > A[i]的所有j中，j取得最小值 比如把4放入1，2，3，9，10

38 算法思路 而在上述过程中，为了查找到合适的放置元素的位置，我们 需要用到二分查找
二分查找的结果，我们的目的是找到这样的一个j，使满足 A[B[j]] > A[i]的所有j中，j取得最小值 比如把4放入1，2，3，9，10 (0+4)/2=2，先和3比，4比3大，查找区间变为 9，10

39 算法思路 而在上述过程中，为了查找到合适的放置元素的位置，我们 需要用到二分查找
二分查找的结果，我们的目的是找到这样的一个j，使满足 A[B[j]] > A[i]的所有j中，j取得最小值 比如把4放入1，2，3，9，10 (0+4)/2=2，先和3比，4比3大，查找区间变为 9，10 (0+1)/2=0，再和9比，4比9小，将9替换为4

40 算法思路 而在上述过程中，为了查找到合适的放置元素的位置，我们 需要用到二分查找
二分查找的结果，我们的目的是找到这样的一个j，使满足 A[B[j]] > A[i]的所有j中，j取得最小值 比如把4放入1，2，3，9，10 (0+4)/2=2，先和3比，4比3大，查找区间变为 9，10 (0+1)/2=0，再和9比，4比9小，将9替换为4 序列变为1，2，3，4，10

41 参考代码 int HALF(int x[], int low, int high, int num) {
int LIS(int * x,int sum) { int k, current = 0, tmp; answer[0] = x[0]; for (k = 1;k < sum;++k) { if (x[k] > answer[current]) answer[++current] = x[k]; else { tmp = HALF(answer, 0, current, x[k]); if (answer[tmp] < x[k]) tmp++; answer[tmp] = x[k]; } return (current + 1); int HALF(int x[], int low, int high, int num) { if (low >= high) { return low; } int mid = (low + high) / 2; if (num < x[mid]) { return HALF(x, low, mid - 1, num);} else return HALF(x, mid + 1, high, num); }

42 Q&A THANKES