标题:一道二分的题 求解答
只看楼主
大雪迢迢
Rank: 1
等 级:新手上路
帖 子: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
书生牛犊
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:星夜征程
等 级:贵宾
威 望:10
帖 子:1101
专家分:5265
注 册:2015-10-27
得分:10 
第一件事,排序。(下面默认为非递减排序情况下的操作)
    然后去整个数列的中间一个元素同x比较,如果大,更新搜索范围为0~n/2-1
      如果相等,返回结果为n/2
       如果小于,更新搜索范围为n/2~n
递归循环啦。
那么具体的二分代码,你可以百度一下,“X语言 二分搜索”(X语言就是你会的哪一种编程语言)。。。要注意的是,本题中你要的是查询“中小于等于x的数中最大的”,不是查询“有没有这个数”,所以除非给定序列最小的一个都比x大,否则都不会返回-1.只要返回最接近的数所在数组下标即可,然后在主函数里输出。

φ(゜▽゜*)♪
2016-08-03 03:44
大雪迢迢
Rank: 1
等 级:新手上路
帖 子:3
专家分:0
注 册:2016-8-3
得分:0 
回复 2楼 书生牛犊
谢谢
2016-08-03 15:44



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-467473-1-1.html




关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.131045 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved