搜索算法

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

顺序搜索

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