顺序搜索

• O(n)

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)

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)

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)

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)时取最小值

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)

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;
}

最后

以上就是彩色老师为你收集整理的六种常用搜索算法顺序搜索快速搜索二分搜索插值搜索跳跃搜索hash搜索的全部内容，希望文章能够帮你解决六种常用搜索算法顺序搜索快速搜索二分搜索插值搜索跳跃搜索hash搜索所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。