请问如何在给定的多个目标区间中判断源区间是否包含其中?
例如:给定多个目标区间[1,2],[4,6],[3,9] 判断源区间[1,6]是否在给定的上述目标区间中。可以看出,不在。
而在给定的目标区间[1,2],[3,9],[2,3],则[1,6]包含于目标区间中。
我的大致思路是:将给定的目标区间,按照区间起始坐标排序,并对相应的区间进行合并。那么如果源区间在给定
的目标区间中的话,那么必定是某一个合并后目标区间的子区间。此时只需要顺序扫描处理后的目标区间即可。
--------------------------------------------------------------------
但是我今天在《编程之美》上看到了这个题目。书上说,在经过排序,合并预处理之后可以进行二分查找。
即在上面的例子中,可以在[1,2],[3,9],[4,6]这个有序,不相交的目标区间中,二分查找[1,6]这个区间以判断是否在
目标区间中。
我想问的是,如何进行这个二分查找过程?如果能够给出伪代码的话,感激不尽!
[解决办法]