扫二维码与项目经理沟通
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
所谓分治就是分而治之，即将较大规模的问题分解成几个较小规模的问题，通过对较小规模的问题的求解达到对整个问题的求解。当我们将问题分解成两个较小问题求解时的分治方法称之为二分法。
猜数字的游戏就可以运用分治法。想一个1000以内的数x，首先猜500，如果运气好可以一次猜中，如果比500大，x的区间就在501-1000里；如果比x小，x的区间就在1-499 ，由于，因此不超过10次就能猜出，这就是二分的基本思想。
假设问题范围是1-n 根据得，所以此算法得时间复杂度就是O(logn)，比逐个枚举得时间复杂度O(n)快了许多。
例题
找数
给一个长度为n得单调递增的正整数数列。有m个询问，每次询问一个x，问数列中最后一个小于 等于x的数是什么？
输入：
第一行两个整数n，m
接下来n个数，表示数列
接下来m行，每行一个询问。
输出：
共m行，表示数列中最后一个小于等于x的数是什么，如没有则输出-1。
例：
5 3
1 2 3 4 6
5
1
3
4
1
3
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
微信二维码
移动版官网