区间数列的查找算法问题

来源：百度知道 编辑：UC知道 时间：2024/05/02 16:18:06
现在一系列递增的区间数列，形如[2,3]、[4,15]、[16,17]、[18,19]这种区数列，前面的区间在数轴都在后面区间的左边，已知另一个区间是上面某个区间的子区间，如[6,12]是[4,15]的子区间，请对于有N个元素的区间数列，和另一个区间[a,b]（保证[a,b]是N个区间中某一个的子区间），如何快速地找出[a,b]是哪个区间的子区间？书上说用二分查找，这种区间数列的二分查找怎么做？或者还有其他方法吗？不论用什么方法，时间复杂度都不得超过O(logN)。能给出C或者C++语言的代码吗？谢谢！

二分查找：
先算出共有几个区间 -- 0 到 M 个
下区间=0；上区间=M

抓出第 （0+M）/2 区间 --也就是：（下区间 + 上区间）/ 2 区间
比较a 是否 大于等于下界，同时比较 b 是否 小于等于上界。如果是，则找到了。
如果 a 大于上界，下区间=刚抓出的区间，上区间不变，
如果 b 小于下界， 上区间 =刚抓出的区间，下区间不变，
抓出第 （下区间 + 上区间）/ 2 区间
如此循环。