回 帖 发 新 帖 刷新版面

主题:[讨论]用C折半查找的问题

在数据结构上看到的一个关于C的算法:折半查找:
int seach-bin(sstable st,keytype key){
                      low=1;high=st.length;
    while(low<=high){
                                     mid=(low+high)/2;
                                     if(EQ(key,st.elem[mid].key) return mid;
                                     else if (LT(key,ST.elem[mid].key)) high=mid-1;
                                     else low=mid+1;
                           }
                                         return 0;
                                     }
其中,low 和high 分别表示顺序表的头位置和尾位置,mid表示中间位置
EQ和LQ为两个宏,EQ(a,b) 即当a=b时,EQ=1,LQ(a,b)当a<b时,LQ=1;
key为需要查找的关键字!
  




讨论:
[size=5]当数组为 05 13 19 21 37 56 64 75 80 85 88 92时,关键字为85,请问这个算法是否可以找得到85这个关键字[/size]

回复列表 (共3个回复)

沙发

说明中有个错误,不是LQ(a,b)而是代码中的LT(a,b);


本人认为,这个算法似乎无法找到要查找的关键字85,因为这个算法类似于中学数学中的二分法求函数解的形式!求哪位高人指点迷津,因为当low=mid+1执行到最后的时候,85变成了low,而算法中对于成功查找的判断仅是 return mid; 这个语句?


求哪位前辈指点,感激不尽!!!!!!!!!!!

板凳

假定你的sstable中,st.elem[0]没有存储实际数据:
初始:low = 1, high = st.length = 12
1: low=1,high=12,mid=6
2: low = mid+1=7, high = 12, mid= (7+12)/2=9
3: low = mid+1=10, high =12, mid =(10+12)/2=11
4: low=10, high=mid-1=10, mid=10 找到85

3 楼


谢谢你,看懂了,那个时候看书的时候忽略了大于85它后退的情况!

我来回复

您尚未登录,请登录后再回复。点此登录或注册