「生活可以更简单, 欢迎来到我的开源世界」
  1. 顺序查找
  2. 二分查找
  3. 分块查找
  4. 插值查找
  5. 斐波那契查找
  6. 二叉树查找
算法-查找
2020-06-29

学习并记录下查找算法,方便回顾。

查找算法 平均时间复杂度 空间复杂度 查找条件
顺序查找 O(n) O(1) 无序
二分查找(折半查找) O(log2n) O(1) 有序
分块查找(索引顺序查找)
插值查找 O(log2(log2n)) O(1) 有序
斐波那契查找 O(log2n) O(1) 有序
哈希查找 O(1) O(n) 无序
二叉查找树(二叉搜索树查找) O(log2n)
红黑树 O(log2n)
2-3树 O(log2n - log3n)
B树/B+树 O(log2n)

顺序查找

顺序查找适合于存储结构为顺序存储或链接存储的线性表,属于无序查找算法。

int SeqSearch(vector<int> &v, int val){
for(int i = 0; i < v.size(); ++i){
if(v[i] == val)return i;
}
return -1;
}

二分查找

元素必须是有序的,如果是无序的则要先进行排序操作,属于有序查找算法。

//迭代方式
int BinarySearch(vector<int> &v, int val, int low, int high){
if(v.size() <= 0)return -1;

while(low <= high){
int mid = low + (high - low)/2;
if(v[mid] == val)return mid;
else if(v[mid] > val)high = mid - 1;
else low = mid + 1;
}
return -1;
}

//递归方式
int BinarySearch(vector<int> &v, int val, int low, int high){
if(v.size() <= 0)return -1;
if(low > high)
return -1;
int mid = low + (high - low)/2;
if(v[mid] == val)
return mid;
else if(v[mid] > val)
return BinarySearch(v, val, low, mid - 1);
else
return BinarySearch(v, val, mid + 1, high);
}

分块查找

插值查找

基于二分查找算法,将查找点的选择改进为自适应选择,可以提高查找效率,属于有序查找。

二分查找:$mid = low + {1 \over 2}(high - low) $

插值查找:$mid = low + {val - v[low] \over v[high] - v[low]}(high - low) $

//迭代方式
int InsertSearch(vector<int> &v, int val, int low, int high){
if(v.size() <= 0)return -1;

while(low <= high){
int mid = low + (val - v[low])/(v[high] - v[low]) * (high - low);
if(v[mid] == val)return mid;
else if(v[mid] > val)high = mid - 1;
else low = mid + 1;
}
return -1;
}

//递归方式
int InsertSearch(vector<int> &v, int val, int low, int high){
if(v.size() <= 0)return -1;
if(low > high)return -1;

int mid = low + (val - v[low])/(v[high] - v[low]) * (high - low);
if(v[mid] == val)
return mid;
else if(v[mid] > val)
return InsertSearch(v, val, low, mid - 1);
else
return InsertSearch(v, val, mid + 1, high);
}

斐波那契查找

基于二分查找算法,通过运用黄金比例的概念选择点进行查找,提高查找效率,属于有序查找算法。

随着斐波那契数列的递增,前后两个数的比值会越来越接近0.618,利用这个特性,将黄金比例运用到查找技术中。

要求开始表中记录的个数为某个斐波那契数小1,及n=F(k)-1

int f[20];

void Fibonacci(){
f[0] = 0;
f[1] = 1;
for(int i = 2; i < 20; ++i)
f[i] = f[i-1] + f[i-2];
}

int FibonacciSearch(vector<int> &v, int n, int val){
int low = 0;
int high = n - 1;

int k = 0;
while(n > f[k] - 1)++k;

vector<int> temp(v);
for(int i = n; i < f[k] - 1; ++i)
temp.push_back(v[n-1]);

while(low <= high){
int mid = low + f[k-1] - 1;
if(val < temp[mid]){
high = mid - 1;
k -= 1;
}
else if(val > temp[mid]){
low = mid + 1;
k -= 2;
}
else{ //判断是否扩展的数值
if(mid < n)return mid;
else return n - 1;
}
}
return -1;
}

二叉树查找

在二叉搜索树b中查找x的过程为:

BSTNode *BSTSearch(BSTNode *node, int val){
while(node != NULL){
if(val < node -> val)node = node -> left;
else if(val > node -> val)node = node -> right;
else return node;
}
return nullptr;
}
<⇧>