int Binary_Search(int *a,int len,int key){    int low,high,mid;    if(!a || len<=0)        //边界处理       return -1;    low=1;high=len;    while(low<=high){            mid = (low+high)/2;            if(key < a[mid])                high = mid - 1;            else if(key > a[mid])                low = mid + 1;            else{                return mid;    //当查找不成功时，返回11           }                   }}

void main(){     int a[] = {0,1,16,24,35,47,59,62,73,88,99};     int length = sizeof(a)/sizeof(int)-1;        //存储下标为1~n     printf("len=%d\n",length );     printf("result=%d\n",Binary_Search(a,length,73));    }

散列函数的构造函数
    Hash函数是创建哈希表的前提，影响着元素查找效率，其函数的值为元素值在哈希表(连续存储空间)中的地址即哈希地址。对于Hash函数的构造，没有特定的要求，所以方法很多，只是我们需了解什么样的哈希函数才叫好的Hash函数，这样就便于我们根据实际情况来构造合理的Hash函数。
1.构造原则
(1)计算简单
    如果设计一个算法可以保证所有的关键字都不会产生冲突，但是这个算法需要很复杂的计算，会耗费很多的时间，这对于需要频繁地查找来说，就会大大降低查找的效率了。因此，散列函数的计算时间不应该超过其他查找技术与关键字比较的时间。
(2)散列地址分布均匀
    尽量让散列地址均匀地分布在存储空间中，以保证存储空间的有效利用，并减少为处理冲突而耗费的时间。
2.常用构造方法
■直接定址法
(1)原理：取关键字(key)或关键字的某个线性函数值为哈希地址，即：
                            H(key)=key或H(key)=a*key+b(a、b为常数)
(2)特点：散列函数的优点就是简单、均匀、不易产生冲突，适用于事先知道关键字的分布和查找表较小且连续的情况。
■数字分析法
    数字分析法的基本思想：使用抽取方法将抽取关键字的一部分来计算散列存储位置的方法，数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的关不且关键字 的若干位分布较均匀，就可考虑这个方法。
■平方取中法
    先通过求关键字的平方值扩大相近数的差别，然后根据表长度取中间的几位数作为散列函数值(哈希地址)。又因为一个乘积的中间几位数和乘数的每一位都相关，所以由此产生的散列地址比较为均匀。适用：不知道关键字的分布，而位数又不是很大的情况。

    即，上述三个关键字的哈希地址分别为4、0、2
■折叠法
(1)原理：折叠法是将关键字从左到右分割成位数相等的几部分(注意最后一部分位数不够时可以短些)，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。
(2)适用场合：事先不需要直到关键字的分布，适合关键字位数较多的情况
■除留余数法(最常用)
    对于散列表长为m的散列函数公式为 
              f(key)=key mod p(p=
注：若散列表表长为m，通常p为小于或等于表长(最好接近m)的最小质数或不包含小于20质因子的合数。p的选取原则：冲突越少越好。
■
基数转换法
    将关键字看作是某个基数制上的整数，然后将其转换为另一基数制上的数

    即，17、24、9为关键字21、30、11的哈希地址(存储空间)
■随机数法
   选择一个随机数，取关键字的随机函数值为它的散列地址，即f(key)=random(key),其中random是随机函数。当关键字的长度不等时，采用这个方法构造散列函数是比较合适的。
总结：
    根据不同因素，决策选择哪种散列函数：
        1.计算散列地址所需的时间;
        2.关键字的长度;
        3.散列表的大小;
        4.关键字的分布情况;
        5.纪录查找的频率。

处理散列冲突方法
1.开放定址法
★线性探测法
(1)定义：开放定址法就是一旦发生了冲突，就去寻址下一个空的散列地址，只要散列表足够大且散列表未被填满，空的散列地址总能找到，并将纪录存入。
    它的公式是：
                            f1(key)=keyMOD m
                            fi(key) = (f(key)+di) MOD m (di=1,2,3,...,m-1)
(2)举例：
    求假如有关键字集合为{12,67,56,16,25,37,22,29,15,47,48,34}，表长为12的哈希表。
    a)取散列函数f(key)=key mod 12;
    b)计算前5个数{12,67,56,16,25}时，都是没有冲突的散列地址，直接存入 ;
    c)计算key=37时，与f(25)所在的位置冲突，故应用f(37)=((37mod12)+1) mod 12=2，即将37存入下标为2的位置。
    .........

★二次探测法
    有些我们在处理冲突时，关键字所在的冲突位置后面没有空位置了，反而它的前面有一个空位置，尽管可以不断地求余数后得到结果，但是效率很差。因此我们可以改进di=1^2,-1^2,2^2,-2^2,....,q^2,-q^2，(q=             fi(key) = (f(key)+di) MOD m (di=1^2,-1^2,2^2,-2^2,....,q^2,-q^2，(q= ★随机探测法
    在冲突时，对于位移量di采用随机函数计算得到，则称为随机探测法。
            fi(key)=(f(key)+di) MOD m(di是一个随机数列)
2.链地址法
    将所有关键字为同义词的记录存储在一个单链表中，我们称这种表为同义词子表，在散列表中只存储所有同义词子表的头指针。链地址法实际上已经不存在什么冲突换址的问题，无论有多少个冲突，都只是在当前位置给单链表增加结点的问题。

   链地址法对于可能会造成很多冲突的散列函数来说，提供了绝不会出现找不到地址的保障，当然，这也就带来了查找时需要遍历单链表的性能损耗。
3.公共溢出区法
    即为所有冲突的关键字建立了一个公共的溢出区来存放。在查找时，对给定值通过散列函数计算出散列地址后，先与基本表的相应位置进行对比，如果相等，则查找成功；如果不想等，则到溢出表去进行顺序查找。如果相对于基本表而言，有冲突的数据很少的情况下，公共溢出区的结构对查找性能来说还是非常高的。

4.再散列函数法
    对于散列表，可以事先准备多个散列函数，每当发生散列地址冲突时，就换一个散列函数计算，相信总会有一个散列函数可以把冲突解决。
                                    fi(key)=RHi(key)(i=1,2,...,k) ，其中RHi就是不同的散列函数。
    这种方法能够使得关键字不产生聚集，但会增加计算时间。

散列表查找实现
1.散列表查找算法实现
(1)散列表结构HashTable
功能：定义一个散列表的结构以及一些相关的常数
算法：
   

 #define SUCCESS 1    #define UNSUCCESS 0    #define HASHSIZE 12    //定义散列表长为数组的长度    #define NULLKEY -32768    typedef struct    {            int *elem;    //数据元素存储基址，动态分配数组            int count;    //当前数据元素个数    }HashTable;    int m=0;            //散列表表长，全局变量(2)初始化散列表    Status InitHashTable(HashTable *H)    {            int i;            m=HASHSIZE;                    H->count=m;                //设置Hash表表长为12            H->elem=(int *)malloc(m*sizeof(int));    //为hash表开辟连续的存储空间            for(i=0;ielem[i]=NULLKEY;            return OK;    }

int Hash(int key){    return key % m;        //除留余数数}

/*插入关键字进散列表*/void InsertHash(HashTable *H,int key){     int addr = Hash(key);    //求散列地址        while(H->elem[addr]!=NULLKEY)    //如果地址部位空，则冲突            addr=(addr+1)%m;        //开发地址法的线性探测解决冲突    H->elem[addr]=key;        //直到有空位后插入关键字}

Status Search(HashTable H,int key,int *addr){    *addr = Hash(key);    //先求要查新关键字的散列地址    while(H.elem[*addr] !=key)    //如果该散列地址位置存在的值不等于关键字，则通过线性探测继续查找    {            *addr = (*addr+1)%m;    //开放地址法的线性探测，查找下一个位置是否相等            if(H.elem[*addr]==NULLKEY||*addr==Hash(key))            {                    return UNSUCCESS;//如果循环回到原点(*addr==Hash(key)),则说明关键字不存在            }    }    return SUCCESS;    //查找成功}

/*二叉树的二叉链表结点结构定义*/typedef struct BiTNode                        //结点结构{    int data;                                            //结点数据    Struct BiTNode *lchild,*rchild;       //左右孩子指针}BiTNode,*BiTree;   

public class BinaryTree{    int data;                //相当于C代码中的数据域数据    BinaryTree left;    //相当于C代码中的指针域指针变量    BinaryTree right;    /*1.构造方法：初始化成员变量*/    public BinaryTree(int data){        this.data = data;        left = null;        right = null;    }    /*2.二叉排序树的查找操作*/    public boolean searchKey(BinaryTree rootObj,int key){        //边界检查        if(root==null)               return false;      if(rootObj.data==key)                 //rootObj的data值相等key，查找成功            return true;       else if(rootObj.data < key)      //rootObj的data值小于key，向右继续查找            return searchKey(rootObj.right,key);        else             return searchKey(rootObj.left,key);    }}/*3.二叉排序树的插入结点*/public void insertTree(BinaryTree rootObj,int data){    if(root.data<=data){        if(rootObj.right == null)            rootObj.right = new BinaryTree(data);        else            insertTree(rootObj.right,data);    }else{        if(rootObj.left == null)            rootObj.left = new BinaryTree(data);        else            insertTree(rootObj.left,data);    }}