六种常用搜索算法顺序搜索快速搜索二分搜索插值搜索跳跃搜索hash搜索

131 阅读 0 评论 87 点赞

我是靠谱客的博主彩色老师，这篇文章主要介绍六种常用搜索算法顺序搜索快速搜索二分搜索插值搜索跳跃搜索hash搜索，现在分享给大家，希望可以做个参考。

搜索算法

顺序搜索
快速搜索
二分搜索
插值搜索
跳跃搜索
hash搜索

顺序搜索

O(n)

复制代码

1
2
3
4
5
6
7
8
int order_search(vector<int>& data, int target) {
int n = (int)data.size();
for(int i = 0; i < n; ++i) {
if(target == data[i])
return i;
}
}

快速搜索

平均O(n), 最坏O(n^2), 序列不需要有序
获取第k+1大的元素(下标k-1)

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int quick_search(vector<int>& data, int l, int r, int key) {
int i = l;
int j = r;
int temp = data[l];
while(i < j) {
while(i < j && data[j] >= temp) --j;
data[i] = data[j];
while(i < j && data[i] <= temp) ++i;
data[j] = data[i];
}
data[i] = temp;
if(i < key) quick_search(data, i+1, r, key);
else if (i > key) quick_search(data, l, i-1, key);
else return data[i];
}

二分搜索

序列需要有序, 时间复杂度O(logn)

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
int binary_search(vector<int>& data, int target) {
int l = 0;
int r = (int)data.size()-1;
while(l <= r) {
int mid = l + (r-l)/2;
if(data[mid] < target) l = mid + 1;
else if (data[mid] > target) r = mid - 1;
else return l;
}
return -1;
}

插值搜索

序列需要有序, 时间复杂度O(loglogn)

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
int intelpolation_search(vector<int>& data, int target) {
int l = 0;
int r = (int)data.size()-1;
while(l <= r) {
int pos = l + (target - data[l])/(data[r] - data[l]) * (r-l);
if(data[mid] < target) l = mid + 1;
else if (data[mid] > target) r = mid - 1;
else return l;
}
return -1;
}

跳跃搜索

在n个元素排序元素中, 以n/m的步伐搜索, 0, n/m, 2n/m… 当找到第一个大于target时, 遍历m-1次
时间复杂度O(根号n), n/m + m -1 当m=sqrt(n)时取最小值

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int jump_search(vector<int>& data, int target) {
int n = (int)data.size();
int step = (int)sqrt(n);
int i = step;
while(i < n) {
if(data[i] > target)
break;
i += step;
}
i = min(i, n);
for(int j = i-1; i >= i - step; --i) {
if(data[j] == target)
return j;
}
return -1;
}

hash搜索

无序没有重复元素, 时间复杂度O(1)

复制代码

1
2
3
4
5
6
7
8
9
10
11
int hash_search(vector<int>& v, int target) {
map<int, int> mp;
for(int i = 0; i < v.size(); ++i) {
mp.insert(pair<int, int>(v[i], i));
}
if(mp.find(target) != mp.end())
return mp[target];
else
return -1;
}