原地址

luogu

二分法(折半查找)

将所给关键词和指定有序集合中间数进行比较,如果比较相等则返回结果,如果不相等,则按照所给出的结果,将集合减半后继续查找
二分法是减治法的思想
二分法：(low+high)/2,如果故意卡数据即low与high很大的话,会越界.所以可以为(high - low)/2+low;
有三种:

优化(先确定范围)

插值查找
这里的插值查找法,是对二分法的一种改进.此法和二分法一样对数据要求有序且尽量分布均匀
对于二分法有: mid = (low + high)/2;
不难得到 mid = low + 1/2*(high-low);
试想,对于在字典中进行查找时,对于’you’或’and’
来说,我们通常的处理方法肯定不是从中间开始进行查找,而是根据所给出的值,大致确定范围后再来进行查找.
这里的大致范围是通过,所查找的value值在所查集合中所大概处于的位置,定位到后进行比较
故有如下公式:
key = low + ((value - a[low])/(a[high]-a[low]))*（high-low);

伪代码:

int insertseek(int value,int map[])
  int low,high,key;
  low = 0; 
  high = n -1 ;
  while(low<=high)
    key = low + ((value - low)/(high-low))*（high -low);
  if(key == value) return key;
  else if(key < value) low = key;
  else  high = key;

例题

五：第12周任务-分巧克力
时间限制：1秒 内存限制：128兆
48 次提交 4 次通过
题目描述
开学那天有n位计科的新生到ZXF做客。ZXF拿出了珍藏的巧克力招待学弟学妹们。ZXF一共有k块巧
克力，其中第i块是Hi * Wi的方格组成的长方形。ZXF需要从这 k 块巧克力中切出n块巧克力分给新生们。为了
公平起见，切出的巧克力需要满足：
1.形状是正方形，边长是整数
2.大小相同
例：一块6x5的巧克力可以切出6块2x2的巧克力或者2块3x3的巧克力。
当然学弟学妹们都希望得到的巧克力尽可能大，你能帮ZXF计算出最大的边长是多少么？
输入
输入在第一行给出两个正整数k和n（0<=n，k<=1000）。
以下k行每行包含两个整数Hi和Wi。(0 <= Hi, Wi <= 1000000) 
输入保证每位新生至少能获得一块1x1的巧克力。
输出
输出切出的正方形巧克力最大可能的边长。
样例输入
2 10
6 5
5 6
样例输出
2

标程：
简单的二分搜索暂时可以模仿我这种模板来写，check函数单独分开来写会让代码的思路更加清晰。二分的主体基本不变，都是改变上下界往两边搜索。另外我代码中出现的头文件是一个万能头文件，基本包含了C/C++当中的我们写算法中需要用到的头文件。目前大部分oj都支持，但是也有部分oj和比赛不支持。（比赛慎用！）