数算---数据查找
顺序查找
顺序查找（Sequential Search），又称为线性查找。是最基本的查找技术，它的查找过程，从表中的第一个（或最后一个）记录开始，逐个进行记录关键字和给定值比较。若某个记录的关键字和给定值相等，说明查找成功，如果直到最后一个（或第一个）记录，没有关键字与给定值相等，说明查找不成功。
//a为数组,n为查找的数组个数,key为要查找的关键字;
int Sequential_Search(int *a,int n,int key){
for (int i = 0; i <= n - 1 ; i++)
if (a[i] == key)
return i;
//没找到返回-1
return -1;
}
折半查找
折半查找（Binary Search）技术，又称二分查找。
前提条件是线性表中的记录必须是关键码有序的（通常从小到大有序），线性表必须采用顺序存储。
基本思想：
- 在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等则查找成功。
- 若给定值小于中间记录关键字，则在中间记录的左半区继续查找。
- 若给定值大于中间记录关键字，则在中间记录的右半区继续查找。
- 重复以上操作，直到查找成功，或者查找结束还未找到即查找失败。
//假设数组a,已经是有序的(从小到大)
int Binary_Search(int *a,int n,int key){
int low,high,mid;
//定义最低下标为记录首位
low = 0;
//定义最高下标为记录末位
high = n - 1;
while (low <= high) {
//折半计算
mid = (low + high) /2;
if (key < a[mid]) {
//若key比a[mid] 小,则将最高下标调整到中位下标小一位;
high = mid-1;
}else if(key > a[mid]){
//若key比a[mid] 大,则将最低下标调整到中位下标大一位;
low = mid+1;
}else
//若相等则说明mid即为查找到的位置;
return mid;
}
return 0;
}
折半查找优化
折半查找公式为mid = (low + high) / 2 = low + 1/2 (high - low)
考虑将1/2进行改进，方案如下：
假设，a[11] = {0, 1, 16, 24, 35, 47, 59, 62, 73, 88, 99} , low = 0, high = 10, 则 a[0] = 0, a[10] = 99, 如果需要查找key = 16，按照常规折半查找需要进行4次才能找到结果，但是如果用新的共识，则
对2.616取整，则
mid = 2，那么我们只需要进行2次就能找到结果。
我们称优化后的方法为插值查找（Interpolation Search），是根据查找的关键字key与查找表中的最大最小记录的关键字比较后的查找方法，核心在于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]) {
//若key比a[mid]插值小,则将最高下标调整到插值下标小一位;
high = mid-1;
}else if(key > a[mid]){
//若key比a[mid]插值 大,则将最低下标调整到插值下标大一位;
low = mid+1;
}else
//若相等则说明mid即为查找到的位置;
return mid;
}
return 0;
}
斐波拉契查找
斐波拉契查找（Fibonacci Search）是利用斐波拉契数列为查找的下标数组，而不是折半查找中根据搜索数组下标来查找，说白了就是利用斐波拉契数列来生成新的mid。
例如下面F为斐波拉契数列，a为要查找的记录数组，长度为10，low = 1, high = 10, 给定值key = 99，查找a中是否有99，返回相应的下标：
计算过程：
-
由于n = 10, key = 99，F[6] < n < F[7]，得到k = 7, 因为F[7] = 13， 而a最大仅有a[10]， 后面的a[11],a[12] 是为赋值的，为了避免之后的数值比对数组越界问题，需要将后续的2个元素赋值，a[11] = a[12] = 99。
-
此时mid = low + F[k - 1] - 1 = 1 + F[7 - 1] - 1 = 1 + 8 -1 = 8;
key > a[8] ---> 99 > 73;
low = mid + 1 = 8 + 1 = 9;
k = k - 2 = 7 - 2 = 5;
-
mid = low + F[k - 1] - 1 = 1 + F[5 - 1] - 1 = 9 + 3 - 1 = 11;
key = a[11] ---> 99 = 99;
mid >n , 11 > 10, 则返回n，返回10.
表示找到key= 99是在数组a中的位置是10的位置上。
key = 99是处在边缘的值，我们可以假设key = 59，来看看在a数组中间的数值计算过程又是怎样的？
计算过程：
-
n = 10, 同上面一样，得到k = 7, F[7] = 13, 补齐后两位数值为a[11] = a[12] = a[10] = 99;
-
mid = low + F[k - 1] - 1 = 1 + F[7 - 1] - 1=1 + 8 - 1 = 8;
key < a[8] ---> 59 < 73;
high = mid - 1 = 8 - 1 = 7;
k = k - 1 = 6;
-
mid = low + F[k - 1] = 1 + F[6 - 1] - 1 = 1 + 5 -1 = 5;
key > a[5] ---> 59 > 47;
low = mid + 1 = 5 + 1 = 6;
k = k - 2 = 4;
-
mid = low +F[k - 1] - 1 = 6 + F[4 - 1] - 1 = 7;
key < a[7] ---> 59 < 62
high = mid - 1 = 6;
k = k - 1 = 3;
-
mid = low + F[k - 1] - 1 = 6 + 1 - 1 = 6;
key = a[6];
mid < n ; 6 < 10, 返回 6;
找到key = 59在数组a中的位置为6。
结论：斐波拉契查找就是利用mid = low + F[k -1] - 1 这个公式来计算出mid的所在位置。然后比较给定值与a[mid]的大小，然后继续或结束。
int F[100]; /* 斐波那契数列 */
//初始化数列
F[0]=0;
F[1]=1;
for(i = 2;i < 100;i++)
{
F[i] = F[i-1] + F[i-2];
}
//计算过程
int Fibonacci_Search(int *a,int n,int key){
int low,high,mid,i,k;
//最低下标为记录的首位;
low = 1;
//最高下标为记录的末位;
high = n;
k = 0;
//1.计算n为斐波拉契数列的位置;
while (n > F[k]-1) {
k++;
}
//2.将数组a不满的位置补全值;
for(i = n;i < F[k]-1;i++)
a[i] = a[n];
//3.
while (low <= high) {
//计算当前分隔的下标;
mid = low+F[k-1]-1;
if (key < a[mid]) {
//若查找的记录小于当前分隔记录;
//将最高下标调整到分隔下标mid-1处;
high = mid-1;
//斐波拉契数列下标减1位;
k = k-1;
}else if(key > a[mid]){
//若查找的记录大于当前的分隔记录;
//最低下标调整到分隔下标mid+1处
low = mid+1;
//斐波拉契数列下标减2位;
k = k-2;
}else{
if (mid <= n) {
//若相等则说明,mid即为查找的位置;
return mid;
}else
{
//若mid>n,说明是补全数值,返回n;
return n;
}
}
}
return 0;
}
总结
综上几种数据查找的方法，说白了就是对mid的计算公式的不同，从而达到不同的效率。
