三种查找算法

一、二分查找

  每次数据都从中间取，取值比目标值小的话就就往右边查找，大的话就从左边查找 ( 从左往右数值依次增大)

   代码如下：

//二分查找
int Search_half(int*array,int size,int val)
{
	int left=0;
    int right=size-1;
	int mid;
	while(left<=right)
    {	//确定mid位置
		mid=(left+right)/2;
        //该位置值比目标值小，向右半部分查找
        if(array[mid]<val)
        {
			left=mid+1;
        }
        //该位置值比目标值大，向左半部分查找
        else if(array[mid]>val)
        {
			right=mid-1;
        }
        //找到目标值所在位置
        else
            return mid;
    }
    //未找到目标值
    return -1;
}

二 . 插值查找法

   与二分查找法相同，由于算法家们的改进，只需将原来的mid改为

mid= left + ( ( val-array[left])/(array[right]-array[left] ) )* ( right-left )

//插值查找
int Search_insert(int*array,int size,int val)
{
	int left=0;
    int right=size-1;
	int mid;
	while(left<=right)
    {	//确定mid位置
		mid=left+((val-array[left])/(array[right]-array[left]))*(left+right);
        //该位置值比目标值小，向右半部分查找
        if(array[mid]<val)
        {
			left=mid+1;
        }
        //该位置值比目标值大，向左半部分查找
        else if(array[mid]>val)
        {
			right=mid-1;
        }
        //找到目标值所在位置
        else
            return mid;
    }
    //未找到目标值
    return -1;
}

三 . 斐波那契查找

原理与上面两种类似，不过分割范围有所不同，斐波那契查找利用黄金分割法，左占0.618，利用该方法查找时需要构建一个斐波那契数组 Fibonacci={ 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 , . . . . . .} , mid= left + F[k-1] -1 ;

① 从斐波那契数列中找到第一个比数组尺寸大的数，记录下标为k

② 越界部分用数组最后一个元素填充，mid=left+F[k-1]-1

③ 如果当前位置的值比目标值小，则从右边查找，并更改查找范围,即k=k-2;

    如果当前位置的值比目标值大，则从左边查找，更改查找范围，即k = k - 1 ;

 重复执行③，直到找到为止

 代码如下：

//斐波那契查找
int Search_Fibonacci(int*array,int size,int val)
{
	//生成相应斐波那契数组
    int*F=malloc(sizeof(int)*100);
    F[0]=1;
    F[1]=1;
    for(int i=2;i<100;i++)
        F[i]=F[i-1]+F[i-2];
	//找到第一个比数组尺寸大的斐波那契数所在位置
    int k=0;
    while(F[k]<=size)
        k++;
	//将越界部分填充
    for(int i=size;i<F[k];i++)
    {
		array[i]=array[size-1];
    }
    int left=0;
    int right=F[k]-1;
    int mid;
    
    while(left<=right)
    {
		mid=left+F[k-1]-1;
        
        if(array[mid]<val)
        {//缩小查找范围，向右侧查找
			left=mid+1;
            k=k-2;
        }
        else if(array[mid]>val)
        {//缩小查找范围，向左侧查找
			right=mid-1;
            k=k-1;
        }
        else
            return mid;//找到
    }
    //未找到
    return -1;
}