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

應用：美團外賣訂單中，按同一時刻來對訂單分塊，但同一時刻中的訂單間是無序的。