查找学习笔记

1、静态查找表

以下查找的索引均从1开始

（1）顺序查找（带哨兵）

#include<iostream>
#include<vector>using namespace std;int search(vector<int> arr, int key) {arr[0] = key;int i;for (i = arr.size() - 1; arr[i] != key; i--);return i;
}int main()
{int n;cin >> n;vector<int> list(n+1);for (auto i = list.begin() + 1; i != list.end(); i++) {cin >> *i;}int t;cin >> t;while (t--) {int key;cin >> key;int check = search(list, key);if (check != 0) {cout << check << endl;}else {cout << "error" << endl;}}return 0;
}

（2）折半查找（二分查找）

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;int search(vector<int> arr, int key) {int beg = 1, end = arr.size() - 1;int mid;while (beg <= end) {mid = (end + beg) / 2 ;if (arr[mid] == key) break;else if (arr[mid] < key) {beg = mid + 1;}else end = mid - 1;}if (arr[mid] == key)return mid;else return 0;
}int main()
{int n;cin >> n;vector<int> list(n+1);for (auto i = list.begin() + 1; i != list.end(); i++) {cin >> *i;}int t;cin >> t;while (t--) {int key;cin >> key;int check = search(list, key);if (check != 0) {cout << check << endl;}else {cout << "error" << endl;}}return 0;
}

扩展：次优查找树

考虑每个元素被查询的概率不同，概率高的元素应尽早被查询

转载：查找算法 | 静态树表（次优查找树）详细分析-CSDN博客

（3）索引顺序查找（分块查找）

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;struct Ind {int maxnum;int start;
};int search(vector<int> list, vector<Ind> ind, int key, int &time){ int i;for (i = 0; i != ind.size(); i++) {time++;if (key <= ind[i].maxnum) break;}if (i == ind.size()) return -1;int j = ind[i].start;for (; j <= list.size() - 1 && list[j] <= ind[i].maxnum; j++) {time++;if (list[j] == key)break;}if (j > list.size() - 1 || list[j] != key) return -1;else return j;
}int main()
{int n;cin >> n;vector<int> list(n + 1);for (auto i = list.begin() + 1; i != list.end(); i++) {cin >> *i;}// 构建索引表int m;cin >>  m;vector<Ind> ind(m);int tmp = 1;for (auto& i : ind) {cin >> i.maxnum;i.start = tmp;tmp += n / m;}int t;cin >> t;while (t--) {int key;cin >> key;int time = 0; // time记录查询次数int check = search(list, ind, key, time);if (check == -1) {cout << "error" << endl;}else {cout << check << "-" << time << endl;}}return 0;
}

应用：美团外卖订单中，按同一时刻来对订单分块，但同一时刻中的订单间是无序的。