| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 444 人关注过本帖
标题:能否用二分法实现区间查找?
取消只看楼主 加入收藏
gelu0
Rank: 1
等 级:新手上路
帖 子:5
专家分:0
注 册:2011-4-9
结帖率:50%
收藏
已结贴  问题点数:10 回复次数:1 
能否用二分法实现区间查找?
比如说我有1,3,5,7,9这样的排列,能否用二分法查找到2所在的位置?
bsearch貌似只能找到完全对应项,不能查找区间。
搜索更多相关主题的帖子: 二分法 
2011-05-02 19:36
gelu0
Rank: 1
等 级:新手上路
帖 子:5
专家分:0
注 册:2011-4-9
收藏
得分:0 
回复 楼主 gelu0
比如,我想要bsearch返回key所在的区间[start, end), 下面这段程序该怎么改呢

void   *   __fileDECL   bsearch   (
        REG4   const   void   *key,
        const   void   *base,
        size_t   num,
        size_t   width,
        int   (__fileDECL   *compare)(const   void   *,   const   void   *)
        )
#endif     /*   __USE_CONTEXT   */
{
        REG1   char   *lo   =   (char   *)base;
        REG2   char   *hi   =   (char   *)base   +   (num   -   1)   *   width;
        REG3   char   *mid;
        size_t   half;
        int   result;

        /*   validation   section   */
        _VALIDATE_RETURN(base   !=   NULL   ||   num   ==   0,   EINVAL,   NULL);
        _VALIDATE_RETURN(width   >   0,   EINVAL,   NULL);
        _VALIDATE_RETURN(compare   !=   NULL,   EINVAL,   NULL);

                /*
                We   allow   a   NULL   key   here   because   it   breaks   some   older   code   and   because   we   do   not   dereference
                this   ourselves   so   we   can 't   be   sure   that   it 's   a   problem   for   the   comparison   function
                */

        while   (lo   <=   hi)
        {
                if   ((half   =   num   /   2)   !=   0)
                {
                        mid   =   lo   +   (num   &   1   ?   half   :   (half   -   1))   *   width;
                        if   (!(result   =   __COMPARE(context,   key,   mid)))
                                return(mid);
                        else   if   (result   <   0)
                        {
                                hi   =   mid   -   width;
                                num   =   num   &   1   ?   half   :   half-1;
                        }
                        else
                        {
                                lo   =   mid   +   width;
                                num   =   half;
                        }
                }
                else   if   (num)
                        return   (__COMPARE(context,   key,   lo)   ?   NULL   :   lo);
                else
                        break;
        }

        return   NULL;
}
2011-05-02 20:50
快速回复:能否用二分法实现区间查找?
数据加载中...
 
   



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

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