#include <iostream>
using namespace std;
/*查找：静态查找：1：查找某个元素是否存在；2.检索某个元素的特性；
动态查找：查找时插入删除元素*/
//顺序查找
int Sequential_Search(int* a, int lengh,int key)
{
for (int i = 0; i < lengh; i++)
{
if (key == a[i])
return i;
}
return -1;
}
//顺序查找优化，如果key就在a[0],返回-1；
int New_Sequential_Search(int* a, int lengh, int key)
{
if (a[0] == key)
return -1;
a[0] = key;
int i = lengh;
while (key != a[i])
i--;
return i;
}
//==============有序表查找================
//二分查找
int Binary_Search(int* a, int length, int key)
{
int low = 0, high = length - 1, mid;
while (low<high)
{
mid = (low + high) / 2;
if (key > a[mid])
low = mid+1;
else if (key < a[mid])
high = mid - 1;
else
return mid;
}
return -1;
}
//二分查找优化：插值查找
int Interpolation_Search(int* a, int length, int key)
{
int low = 0, high = length - 1, mid;
while (low < high)
{
mid = low + (key - a[low]) / a[high] - a[low];
if (key > a[mid])
low = mid + 1;
else if (key < a[mid])
high = mid - 1;
else
return mid;
}
return -1;
}
//斐波那契查找：仅用加减法实现二分查找，时间复杂度O(logn)
/*对于斐波那契数列：1、1、2、3、5、8、13、21、34、55、89……（也可以从0开始），
前后两个数字的比值随着数列的增加，越来越接近黄金比值0.618。*/
const int MAXSIZE = 20;
int* Fibonacci(int n)
{
int* fib = new int(n);
for (int i = 0; i < n; i++)
{
if (i < 2)
fib[i] = i;
else
fib[i] = fib[i - 1] + fib[i - 2];
}
return fib;
}
int Fibonacci_Search(int* a, int lengh, int key)
{
int high = lengh - 1, low = 0, mid = 0;
int* f = Fibonacci(20);
int k = 0;
while (lengh > f[k] - 1)
k++;
for (int i = lengh - 1; i < f[k] - 1; i++)
a[i] = a[lengh - 1];
while (low < high)
{
// low：起始位置
// 前半部分有f[k-1]个元素，由于下标从0开始
// 则-1 获取 黄金分割位置元素的下标
mid = low + f[k - 1] - 1;
if (key < a[mid])
{
// 查找前半部分，高位指针移动
high = mid - 1;
// （全部元素） = （前半部分）+（后半部分）
// f[k] = f[k-1] + f[k-2]
// 因为前半部分有f[k-1]个元素，所以 k = k-1
k -= 1;
}
else if (key>a[mid])
{
// 查找后半部分，高位指针移动
low = mid + 1;
// （全部元素） = （前半部分）+（后半部分）
// f[k] = f[k-1] + f[k-2]
// 因为后半部分有f[k-2]个元素，所以 k = k-2
k -= 2;
}
else
{
if (mid < lengh)
// 如果为真则找到相应的位置
return mid;
else
return lengh;// 出现这种情况是查找到补充的元素
// 而补充的元素与high位置的元素一样
}
}
return -1;
}
//===================线性索引查找=====================
/*1.稠密索引：在线性索引中 ，将数据集中的每个记录对应一个索引项 ，索引项一定按照关键码排列。
2.分块索引：（块内无序，块间有序）最大关键码、记录个数、首数据元素指针
3.倒序索引：索引项（次关键码+记录号表：储存具有相同次关键字的所有记录的记录号）*/
