一、线性查找算法
线性查找是逐一比对，发现有相同值，就返回下标，否则返回 -1。这里，我们实现的线性查找是找到一个满足条件的值就返回。
/**
* @brief 线性查找
*
* @param A 待查找的数组
* @param N 数组的长度
* @param value 待查找的元素
* @return int 如果找到返回数组下标，否则返回-1
*/
int OrderSearch(int A[],int N,int value)
{
int i = 0;
for(i = 0; i < N; i++)
{
if(A[i] == value)
{
return i;
}
}
return -1;
}
二、二分查找法
二分查找 要求待找到的数组必须 有序。这里假设待查找的数组是升序的。它的思路如下：
- 首先确定该数组的中间的下标 middle = (left + right) / 2;
- 然后让需要查找的数 findVal 和 A[middle] 比较，确定要查找的数在哪一边
- 如果 findVal > A[middle]，说明你要找到的数在 middle 的右边，因此需要递归的向右查找
- 如果 findVal < A[middle]，说明你要找到的数在 middle 的左边，因此需要递归的向左查找
- 如果 findVal == A[middle]，说明你找到，找到就返回
那我们需要在什么时候结束递归呢？当我们找到元素时就结束递归；当递归完整个数组，仍然没有找到 findVal，也需要结束递归，即当 left > right 是就需要结束递归；
/**
* @brief 二分查找
*
* @param A 待查找的数组
* @param N 数组的长度
* @param value 待查找的元素
* @return int 如果找到返回数组下标，否则返回-1
*/
int BinarySearch(int A[],int N,int value)
{
Binary(A,0,N-1,value);
}
/**
* @brief 二分查找核心算法
*
* @param A 待查找的数组
* @param left 递归的左边的索引
* @param right 递归的右边的索引
* @param value 待查找的元素
* @return int 如果找到返回数组下标，否则返回-1
*/
int Binary(int A[],int left,int right,int value)
{
int middle = (right - left) / 2 + left;
int middleVal = A[middle];
// 当left>right时，说明递归整个数组，但是没有找到
if(left > right)
{
return -1;
}
if(value > middleVal)
{
Binary(A,middle+1,right,value); // 向右递归
}
else if(value < middleVal)
{
Binary(A,left,middle-1,value); // 向左递归
}
else
{
return middle;
}
}
我们也可以用非递归的方式来实现二分查找：
/**
* @brief 二分查找
*
* @param A 待查找的数组
* @param N 数组的长度
* @param value 待查找的元素
* @return int 如果找到返回数组下标，否则返回-1
*/
int Binary(int A[],int N,int value)
{
int left =0;
int right = N-1;
int middle = 0;
while(left <= right)
{
middle = (right - left) / 2 + left;
if(A[middle] == value) // 如果找到则返回
{
return middle;
}
else if(A[middle] < value) // 需要向右边查找
{
left = middle + 1;
}
else
{
right = middle - 1; // 需要向左边查找
}
}
return -1;
}
三、插值查找法
差值查找算法类似于二分查找也要求待查找的数组是有序的，不同的是差值查找每次从自适应 minddle 处开始查找。此时，\(middle = low + \frac{key- a[low]}{a[high] - a[low]}(high - low)\)。其中，key 就是待查找的值 value。
/**
* @brief 插值查找
*
* @param A 待查找的数组
* @param N 数组的长度
* @param value 待查找的元素
* @return int 如果找到返回数组下标，否则返回-1
*/
int InsertValueSearch(int A[],int N,int value)
{
if(value < A[0] || value > A[N-1])
{
return -1;
}
InsertValue(A,0,N-1,value);
}
/**
* @brief 插值查找核心算法
*
* @param A 待查找的数组
* @param left 递归的左边的索引
* @param right 递归的右边的索引
* @param value 待查找的元素
* @return int 如果找到返回数组下标，否则返回-1
*/
int InsertValue(int A[],int left,int right,int value)
{
int middle = 0;
int middleVal = 0;
if(left > right)
{
return -1;
}
middle = left + (right - left) * (value - A[left]) / (A[right] - A[left]);
middleVal = A[middle];
if(value > middleVal)
{
InsertValue(A,middle+1,right,value); // 向右递归
}
else if(value < middleVal)
{
InsertValue(A,left,middle-1,value); // 向左递归
}
else
{
return middle;
}
}
对于数据量较大，关键字分布比较均匀的查找表来说，采用插值查找，速度较快；关键字分布不均匀的情况下，该方法不一定比折半查找要好；
四、斐波那契查找法
斐波那契查找法 也叫 黄金分割法。黄金分割点 是指把一条线段分割为两部分，是其中一部分与全长之比等于另一部分与这部分之比。取其前三位数字的近似值是 0.618。由于按此比例设计的造型十分美丽，因此称为 黄金分割，也称为 中外比。斐波那契数列 {1,1,2,3,5,8,13,21,34,55} 发现斐波那契数列的两个相邻数的比例，无线接近 黄金分割值 0.618。
斐波那契查找法原理与前面两种相似，仅仅改变了中间值（middle）的位置，middle 不再是中间或插值得到的，而是位于黄金分割点附近，即 \(middle = low + F[K-1] -1（F 代表斐波那契数列）\)。
由斐波那契数列 \(F[K] = F[K-1] + F[K-2]\) 的性质，可以得到 \((F[K-1]) = (F[K-1] -1) + (F[K-2]-1) +1\)。该式说明：只要顺序表的长度为 \(F[K]-1\)，则可以将该表分成长度为 \(F[K-1]-1\) 和 \(F[K-2]-1\) 的两段，从而中间位置为 \(middle = low + F[K-1]} -1\)。
类似的，每一字段也可以用相同的方式分割。但顺序表的长度 N 不一定恰好等于 F[K]，所以需要将原来的顺序表的长度 n 增加至 F[K]-1。这里的 K 值只要能使的 F[K-1] 恰好大于或等于 N 即可。顺序表长度增加后，新增的位置（从 N+1 到 F[K]-1 位置），都赋为 N 位置的元素即可。
/**
* @brief 斐波那契查找
*
* @param A 待查找的数组
* @param N 数组的长度
* @param value 待查找的元素
* @return int 如果找到返回数组下标，否则返回-1
*/
int FibonacciSearch(int *A,int N,int value)
{
int low = 0, high = N-1, middle = 0;
int *temp;
int k = 0,i = 0;
int number = getFibonacciSize(N);
int fib[number];
getFibonacci(fib,number); // 获取斐波那契数列
// 获取斐波那契分割数值的下标
while(high > fib[k]-1)
{
k++;
}
// 因为fib[k]值可能大于A的长度，
// 因此，我们需要构造一个新的数组
temp = (int *)calloc(fib[k]-1,sizeof(int));
memcpy(temp,A,N * sizeof(int)); // 将源数组的数据拷贝到临时数组中
// 如果源数组小于临时数组，则用源数组的最后一个元素填充临时数组后面的元素
for(i = N; i < fib[k]-1; i++)
{
temp[i] = A[N-1];
}
// 使用while循环找到value
while(low <= high)
{
middle = low + fib[k-1] - 1;
// 向数组的前面查找（左边）
if(value < temp[middle])
{
high = middle - 1;
// 全部元素 = 前面的元素 + 后面的元素
// F[K] = F[K-1] + F[K-2]
// 因为，前面有F[K-1]个元素，所以可以继续拆分 F[K-1] = F[K-2] + F[K-3]
// 即在F[K-1]前面继续查找
// 下次循环的时候middle=low+F[K-1-1]-1
k -= 1;
}
// 向数组的后面查找（右边）
else if(value > temp[middle])
{
low = middle + 1;
// 全部元素 = 前面的元素 + 后面的元素
// F[K] = F[K-1] + F[K-2]
// 因为，前面有F[K-2]个元素，所以可以继续拆分 F[K-2] = F[K-3] + F[K-4]
// 即在F[K-2]的前面继续查找
// 下次循环的时候middle=low+F[K-1-2]-1
k -= 2;
}
else
{
free(temp);
// 需要确定的返回的是哪个小标
return (middle <= high) ? middle : high;
}
}
free(temp);
return -1;
}
/**
* @brief 获取斐波那契数列
*
* @param fib 待获取的斐波那契数列
* @param N 待获取的斐波那契数列的长度
*/
void getFibonacci(int *fib,int N)
{
int i = 0;
fib[0] = 1;
fib[1] = 1;
for(i = 2; i < N; i++)
{
fib[i] = fib[i-1] + fib[i-2];
}
}
/**
* @brief 找到第几个斐波那契数大于number
*
* @param number 待比较的数
* @return int 返回大于number的那个斐波那契数的序号
*/
int getFibonacciSize(int number)
{
int i = 2;
int temp = 0;
int num[2] = {1,1};
while (num[1] < number)
{
temp = num[1];
num[1] += num[0];
num[0] = temp;
i++;
}
return i;
}