二分查找及其应用.ppt

二分查找及其应用 ByElemenT 今天 你AC了吗 NO YES 请在这里输入您的标题 刷题太无聊 我们玩游戏吧 相信大家都玩过猜数字的游戏 两人游戏 A同学在心里默念一个整数n 1 n 1000 B同学猜n是多少 同时如果B没有猜对 A告诉他这个数比默念的数高了还是低了 最坏情况下 ElemenT也不用超过十次可以猜出 最坏情况下需要多少次呢 看起来好厉害的样子 其实并不是 下面将引入 二分搜索 的概念 如上述的游戏中 第一次应该取多少呢 500 很不巧并不是500 而是一个比500大的数 虽然运气不好 但是B将区间的范围砍掉了一半 那么下一次B该猜什么 大家已经发现 问题变成了501 1000之间猜一个数 那么应该猜 501 1000 2 750 如果运气还是不好 又猜小了 没关系 只猜了仅仅两次 我们就将区间缩小为751 1000 那么继续下去 我们发现 每次可以将区间缩小为原来的一半 递减速度显然就是log级别的 log 1000 向上取整只有10 那么我们一定可以在10次之内猜出这个数 给定一个有序序列a0 a1 a2 aN 给出一个目标值tg 在序列中查找是否存在tg 如果存在 返回tg的下标 如何快速查找 我们必须看到数列是有序的 充分利用有序的条件 类似猜数一样查找tg 复杂度为log n 那么我们来看看如何实现二分查找 intbs int a intn inttg intl 0 r n 1 while ltg r mid 1 elsel mid 1 return 1 二分查找的应用 二分答案 假定一个解判断是否可行最大化最小值最大化平均值 有N条绳子 它们长度分别为Li 如果从他们中切割出K条长度相同的绳子的话 这K条绳子每条最长能有多长 答案保留两位小数 1 N 10 4 1 K 10 4 1 Li 10 5样例输入N 4 K 11 L 8 02 7 43 4 57 5 39 样例输出2 00 每条绳子可以得到4 3 2 2共计11条 另C x 可以得到K条长度为x的绳子 问题转化为求满足C x 条件的最大的x C x Li x的总和是否大于K 因此 计算C x 的复杂度是O n 那么只要二分枚举x 就可以解决此题 intmain cin n k for inti 0 i a i doublel 0 r 100001 for inti 0 i 100 i doublem l r 2 if ok m l m elser m printf 2f n 0 01 int l 100 return0 intn k doublea maxn tot 0 boolok doublex intnum 0 for inti 0 i k returntrue returnfalse 再看一道最大化最小值的例题这类问题通过二分搜索可以很好的解决 农夫约翰搭了一间有N间牛社的小屋 牛舍排在一条直线上 第i号牛舍在xi的位置 但是他的M头小牛对小屋很不满意 因此经常互相攻击 约翰为了防止牛之间互相伤害 因此决定把每头牛都放在离其他牛尽可能远的牛舍 也就是最大化最近的两头牛之间的距离 条件限制 2 N 1000002 M N0 xi 10 9样例输入N 5 M 3 x 1 2 8 4 9 样例输出3 在位置1 4 9放3头牛 另C d 可以安排的牛的位置使得最近的两头牛的距离不小于d问题就变成了求满足C d 的最大的d 每次判断对每头牛最多处理一次 因此判断的复杂度是O n 总复杂度O n log INF intmain cin n c for inti 0 i pos i sort pos pos n intl 0 r MAX 1 while r l 1 intm l r 1 if ok m l m elser m cout l endl return0 intn c intpos maxn boolok intma intcnt 1 intlast