【算法1-6】二分查找与二分答案

题单介绍

大家还知道怎么在一本很厚的词典查找一个单词吗?字典中的单词是按照“字典序”进行排序的,比如 code<pan<pancake 。如果我们要找一个单词,就要将字典从中间翻开,然后将这面单词跟想要找的单词比较。如果这面单词在需要寻找的单词之前,就将字典往后翻,否则就往前翻,直到找到准确的单词为止。 大家可以发现,越接近需要查询的单词,翻动书面的页数就越少。你肯定不会从第一页开始一面一面翻,逐个查看每个单词是否就是自己想要查的单词,这样做就太慢了。虽然实际情况不是那么精确,但是基本上使用了“二分思想”。 如果序列是有序的,就可以通过二分查找快速定位所需要的数据。除此之外,二分思想还能求出可行解的最值问题,比如想知道某款手机最高能多少楼高度摔下来而不会摔坏,使用二分的方式可以用最小实验次数就能得到结果(当然你需要准备好几个样品)。 ![](https://cdn.luogu.com.cn/upload/image_hosting/ll59oa7f.png) **以上题单的选题来自洛谷编写教材《深入浅出程序设计竞赛 - 基础篇》**,并带有详细的教程和讲解,点击下方的图片了解该图书详情。[【官方网店绝赞热卖中!】>>>](https://item.taobao.com/item.htm?id=637730514783) [![](https://cdn.luogu.com.cn/upload/image_hosting/njc7dlng.png)](https://item.taobao.com/item.htm?id=637730514783)

题目列表

  • 【深基13.例1】查找
  • A-B 数对
  • [COCI 2011/2012 #5] EKO / 砍树
  • [NOIP2001 提高组] 一元三次方程求解
  • 烦恼的高考志愿
  • 木材加工
  • [NOIP2015 提高组] 跳石头
  • [TJOI2007] 路标设置
  • 数列分段 Section II
  • 银行贷款
  • 小鸟的设备