三峡大学算法设计与分析论文-倍增思想在算法运用与实现

1.引言 我们常常会遇到这样的问题：给定一个有序数组a\left[N\right],需要查找出最大的不小于某个数的数字或者查找出最小的大于某个数的数字，通常的朴素做法是从头到尾遍历一遍，那么时间复杂度就是O\left(n\right)。 如果我们用倍增的思想去思考，假设我们有一个增长长度∆l和一个已经确定的长度l,我们只需要确定a∆l+l是否满足条件就行，若满足就让∆l × 2;否则l缩小范围,这样时间复杂度就是O\left(logn\right) 。肯定会有人说用二分查找，时间复杂度也是O\left(logn\right)，二者有些相似，但二分是值对应区间，倍增是区间对于值。 如果我们将问题升级一下,数组a\left[N\right]并不是有序的,并且有T次查询，每次都是在\left[l,r\right]的区间去查找我们所要求的数，如果每次都去暴力求解每次询问，从头到尾去遍历,时间复杂度就是O\left(T\times\left(l-r\right)\right),并且区间可能会重复，包含，会很浪费时间,可能面对我们的只有Time\ Limit\ Exceeded了。那有没有一种算法