查找算法
2018 algorithm关于查找算法。
基本概念
查找表：由同一类型的数据元素（或记录）构成的集合。
关键字：数据元素（或记录）的某个数据项的值。主关键字是指能唯一标识一个数据元素的关键字。次关键字是指能标识多个数据元素的关键字。
静态查找：查询数据元素是否在查找表中或者检索属性。
动态查找：在查找表中插入或者删除数据元素。
常见的查找算法
顺序查找
顺序查找，也叫线性查找(Linear Search)。其基本思路：从表的一端开始，逐个进行记录的关键字和给定值的比较，若找到一个记录的关键字与给定值的值相等，则查找成功。若整个表中的记录均比较过，仍未找到关键字等于给定值的记录，则查找失败。
顺序查找的方法对于顺序存储方式和链式存储方式的查找表都适用。
顺序查找成功的平均查找长度为：ASLss = (n + 1) / 2
优劣势：顺序查找方法在 n 值较大时，其平均查找长度较大，查找效率较低。优点就是算法简单且适应面广，堆查找表的结构没有要求，无论记录是否有序排列均可应用。
int Search(int arr[], int len, int key) {
for (int i = 0; i < len; i++)
if (arr[i] == key)
return i;
return -1;
}
二分查找
重要前提：查找表的元素已经按关键字递增（或递减）方式排序。
二分查找(Binary Search)也叫折半查找。主要思想：首先将查找元素关键字(key)值与表中间位置(下标 mid)记录的关键字进行比较，若相等，则查找成功。若关键字大于中间记录的关键字，则在中间记录的右半区继续查找。若关键字小于中间记录的关键字，则在中间记录的左半区继续查找。重复上述过程，直至查找成功或者子表为空失败为止。
二分查找成功的平均长度为：ASLbs = (n + 1) / n * log2(n + 1) - 1
当 n 较大时，可以近似看成：ASLbs ≈ log2(n + 1) - 1
int BSearch(int arr[], int low, int high, int key) {
int mid;
while(low <= high) {
mid = (low + high) / 2;
if (key = arr[mid]) return mid;
else if (key < arr[mid]) high = mid - 1;
else low = mid + 1;
}
return -1;
}
//======================
// 用二分查找的递归实现
//======================
int BSearch_rec(int arr[], int low, int high, int key) {
int mid;
if (low <= high) {
mid = (low + high) / 2;
if (key = arr[mid]) return mid;
else if (key < arr[mid]) return BSearch_rec(arr, low, mid - 1, key);
else return BSearch_rec(arr, mid + 1, high, key);
}
return -1;
}
插值查找
插值查找(Interpolation Search)是一种基于二分查找的算法。二分查找根据查找关键字确定不同的位置。
在二分查找里面，mid = (low + high) / 2，即 mid = low + (high - low) / 2 插值查找的计算，mid = low + (key - a[low]) / (a[high] - key) * (high - low)
int ISearch(int arr[], int low, int high, int key) {
int mid;
while(low <= high) {
mid = low + (key - a[low]) / (a[high] - key) * (high - low);
if (key = arr[mid]) return mid;
else if (key < arr[mid]) high = mid - 1;
else low = mid + 1;
}
return -1;
}
哈希表查找
基本思想：已知关键字集合 U，最大关键字 m，设计一个函数 Hash，它以关键字为自变量，关键字的存储地址为因变量，将关键字映射到一个有限的、地址连续的区间 T[0..n-1]中，这个区间被称为哈希表，哈希表查找使用的转换函数被称为哈希函数。
对于哈希表，主要考虑两个问题：一是如何构造哈希函数，二是如何解决冲突。
常用的哈希构造方法有直接定址法、数字分析法、平方取中法、折叠法、随机数法和除留余数法等。
解决冲突就是为出现冲突的关键字找到另一个“空”的哈希地址。
常用的处理冲突的方法有开放定址法，链地址法，再哈希法和建立一个公共溢出区。
斐波那契查找
斐波那契查找(Fibonacci Search)也是一种基于二分查找的算法。利用斐波那契数列选择查找点进行查找，提高查找效率。
斐波那契数列数组可以直接定义：F = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368]
void initFib(int *fib, int size) {
int i;
fib[0] = 1;
fib[1] = 1;
for (i = 2; i < size; i++)
fib[i] = fib[i - 1] + fib[i - 2];
}
#define FIB_MAXSIZE 100
int FSearch(int *arr, int n, int key) {
int low = 0;
int high = n - 1;
int fib[FIB_MAXSIZE];
initFib(fib, FIB_MAXSIZE);
// 找到有序表元素个数在斐波那契数列中最接近的最大数列值
int k = 0;
while (high > fib[k] - 1) k++;
// 补齐有序表
for (i = length; i <= fib[k] - 1; i++) {
arr[i] = data[high];
}
while (low <= high) {
mid = low + fib[k - 1] - 1;
if (arr[mid] == key) {
if (mid <= length - 1) return mid;
else return length - 1;
}
if (arr[mid] > key) {
high = mid - 1;
k = k -1;
}
if (arr[mid] < key) {
low = mid + 1;
k = k - 2;
}
}
return -1;
}