int Binary_Search(int *a,int n,int key)//n为元素最高下标而不是数组长度{    int low,mid,high;    low = 0;           //最低下标    high = n;          //最高下标    mid = (low + high) / 2;//折半    while(low <= high)    {        if(key < a[mid])            high = mid - 1;        else if(key >a[mid])            low = mid + 1;        else            return mid;    }     return 0;}//使用该算法的前提是：顺序存储及元素有序

        已知具有n个结点的完全二叉树的深度为[log2n]+1（括号表示不大于x的最大整数）。尽管折半查找判定二叉树并不是完全二叉树，但同样的推导可以得出，该算法的最坏情况是查找到关键字或者查找失败的次数为[log2n]+1。因此该算法的平均时间复杂度为O(logn)。

int Binary_Search(int a[], int value, int low, int high){//递归版本    int mid = low+(high-low)/2;    if(a[mid]==value)        return mid;    if(a[mid]>value)        return Binary_Search(a, value, low, mid-1);    if(a[mid]

        折半查找适用于静态查找表。而对于经常需要执行插入和删除操作的数据集来说，维护有序的排序付出的代价太高，不建议使用。

插值查找

/* 插值查找 */int Interpolation_Search(int *a,int n,int key){	int low,high,mid;	low=1;	/* 定义最低下标为记录首位 */	high=n;	/* 定义最高下标为记录末位 */	while(low<=high)	{		mid=low+ (high-low)*(key-a[low])/(a[high]-a[low]); /* 插值 */		if (key
      
       a[mid])/* 若查找值比插值大 */			low=mid+1;		/* 最低下标调整到插值下标大一位 */		else			return mid;		/* 若相等则说明mid即为查找到的位置 */	}	return 0;}
      

斐波那契查找

        

                                   

        斐波那契查找算法的核心在于：

• 当key为a[mid]时，查找成功。
• 当key < a[mid]时，新范围为下标low到mid-1，即此时范围个数为F[k-1]-1个。
• 当key > a[mid]时，新范围为下标mid+1到high，即此时范围个数为F[k-2]-1个。

const int max_size=20;//斐波那契数组的长度/*构造一个斐波那契数组*/ void Fibonacci(int * F){    F[0]=0;    F[1]=1;    for(int i=2;i
      
       F[k]-1)//计算n位于斐波那契数列的位置      ++k;  int  * temp;//将数组a扩展到F[k]-1的长度   temp=new int [F[k]-1];//必须满足条件n>F[k]-1。  memcpy(temp,a,n*sizeof(int));//即如果待排序数组的长度等于斐波那契数据项的值,那么一定会使将数组填充到斐波那契下一个数据项的有值长度。   for(int i=n;i
       
        temp[mid])    {     low=mid+1;     k-=2;    }    else    {       if(mid
        
         =n则说明是扩展的数值,返回n-1    }  }    delete [] temp;  return -1;}
        
       
      

小结