搜索
编程论坛
→
开发语言
→
『 数据结构与算法 』
→ 一道二分的题 求解答
标题:
一道二分的题 求解答
只看楼主
大雪迢迢
等 级:
新手上路
帖 子:3
专家分:0
注 册:2016-8-3
结帖率:
0
楼主
已结贴
√
问题点数:10 回复次数:2
一道二分的题 求解答
[local]1[/local]给出n个数,m次询问,每次询问给出一个x,求这n个数中小于等于x的数中最大的数是什么。
n、m≤10^5
搜索更多相关主题的帖子:
最大的
2016-08-03 02:03
书生牛犊
来 自:星夜征程
等 级:
贵宾
威 望:
10
帖 子:1101
专家分:5265
注 册:2015-10-27
第
2
楼
得分:10
第一件事,排序。(下面默认为非递减排序情况下的操作)
然后去整个数列的中间一个元素同x比较,如果大,更新搜索范围为0~n/2-1
如果相等,返回结果为n/2
如果小于,更新搜索范围为n/2~n
递归循环啦。
那么具体的二分代码,你可以百度一下,“X语言 二分搜索”(X语言就是你会的哪一种编程语言)。。。要注意的是,本题中你要的是查询“
中小于等于x的数中最大的
”,不是查询“有没有这个数”,所以除非给定序列最小的一个都比x大,否则都不会返回-1.只要返回最接近的数所在数组下标即可,然后在主函数里输出。
φ(゜▽゜*)♪
2016-08-03 03:44
大雪迢迢
等 级:
新手上路
帖 子:3
专家分:0
注 册:2016-8-3
第
3
楼
得分:0
回复 2楼 书生牛犊
谢谢
2016-08-03 15:44
3
1/1页
1
参与讨论请移步原网站贴子:
https://bbs.bccn.net/thread-467473-1-1.html
关于我们
|
广告合作
|
编程中国
|
清除Cookies
|
TOP
|
手机版
编程中国
版权所有,并保留所有权利。
Powered by
Discuz
, Processed in 0.096366 second(s), 8 queries.
Copyright©2004-2025, BCCN.NET, All Rights Reserved