原地址
二分法(折半查找)
- 将所给关键词和指定有序集合中间数进行比较,如果比较相等则返回结果,如果不相等,则按照所给出的结果,将集合减半后继续查找
- 二分法是减治法的思想
- 二分法:
(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);
伪代码:
1 | int insertseek(int value,int map[]) |
例题
1 | 五:第12周任务-分巧克力 |
v1.5.2