论坛 › 数据结构与算法 › 数据结构与算法

风刃之舞§～ 发表于 2013-6-17 10:48:32

数据结构与算法

折半查找的算法 ，用C实现，在哪里？

wqcqu_edu 发表于 2013-6-17 12:42:42

期待。。。。。。。。。。。。。。。。。。。。

浴血重生13 发表于 2013-6-17 13:24:31

package binarySearch;

public class binarySeachComparable <T extends Comparable<T>>{
       
        //问题,如何来使用comparable<T>接口
       
        //采用折半查找的算法思想来解决这个查找问题
        //折半查找的条件:
        //1、将无序的数列排为有序的数列、这里采用的是线性表顺序存储结构
        //2、采用折半查找的算法
       
        public int binarySearch(T []value,T key){
                System.out.println("最后所得到的下标为："+binarySearch(value, 0,value.length-1,key));
                return binarySearch(value, 0,value.length-1,key);
        }

        private int binarySearch(T []value,int begin,int end,T key) {
                if(value==null||key==null){
                        return -1;
                }
                while(begin<=end){
                        int mid=(begin+end)/2;
                        System.out.println(mid+"?");
                        if(value.compareTo(key)==0){
                                return mid;
                        }
                        if(value.compareTo(key)>0){
                                //key值比mid值要小些
                                end=mid-1;
                        }
                        else{
                                begin=mid+1;
                        }
                }
                return -1;
        }
}

浴血重生13 发表于 2013-6-17 13:25:49

这是java版的， C的思想应该和之差不多，可以参考下，需要注意的是才用折半查找的前提条件

浴血重生13 发表于 2013-6-17 13:39:12

c语言版的折半查找

#include<stdio.h>
#include<stdlib.h>

#define N 19

int main(){
int a={2,5,6,7,8,13,15,17,21,23,25,26,27,28,35,41,52,63};
int mid,bot,top,x;

top=0;
bot=N-1;

printf("请输入要找的元素：");
scanf("%d",&x);

while(top<=bot){
mid=(top+bot)/2;

if(x==a){
printf("\n找到的元素 %d是：a[%2d]\n",x,mid);
exit(0);
}


else if(x>a){
top=mid+1;
}
else{
bot=mid-1;
}
}
printf("没有找到该元素！\n");

return 0;

}

Skyline 发表于 2013-6-20 21:03:08

学习学习。。。。。。。。。。

查看完整版本: 数据结构与算法