二分查找
二分查找
BinarySearch
原理
类似二分法
用于顺序存储结构
使用心得
面对问题时有两种思考方式
- 不断缩小查找范围直到找到最优解
- 不断排除“必不可能为最优解的解”,直至最后
我一直在想怎么来说明二分查找“一定不会漏掉最优解”,这里的第二种思考方式能很好地解释这一问题。
例题
Q:查找最接近的元素
描述
在一个非降序列中,查找与给定值最接近的元素。
输入
第一行包含一个整数n,为非降序列长度。1 <= n <= 100000。
第二行包含n个整数,为非降序列各元素。所有元素的大小均在0-1,000,000,000之间。
第三行包含一个整数m,为要询问的给定值个数。1 <= m <= 10000。
接下来m行,每行一个整数,为要询问最接近元素的给定值。所有给定值的大小均在0-1,000,000,000之间。
输出
m行,每行一个整数,为最接近相应给定值的元素值,保持输入顺序。若有多个值满足条件,输出最小的一个。
样例输入
1 |
|
y样例输出
1 |
|
题解
1 |
|
解释
- L4 ~ L21为二分查找
- 考虑将中间的值与要找的数”x”做差,算绝对值,比较中间值与”x”的大小假设中间值小于”x”,那么中间值左侧的数据与”x”差的绝对值会更大,必不可能为最优解,因此舍弃
- 用中间值计算得到的结果已经判断过,因此查找时
r=m-1
或者l=m+1
不会造成漏解 - L7中
while(l<=r)
说明查找范围包含两端的数据
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!