#include <iostream> #include <algorithm> using namespace std; // 顺序查找 int sequential_search(int* list, int size, int key) { int count = 0; for (int i = 0; i < size; i++) { count++; if (list[i] == key) { cout << "找到元素在 " << i+1 << ".比较次数：" << count << endl; return i; } } cout << "找不到元素。比较次数： " << count << endl; return -1; } // 折半查找 int binary_search(int* list, int left, int right, int key) { int count = 0; while (left <= right) { count++; int mid = (left + right) / 2; if (list[mid] == key) { cout << "找到元素在 " << mid+1 << ".比较次数：" << count << endl; return mid; } else if (list[mid] < key) { left = mid + 1; } else { right = mid - 1; } } cout << "找不到元素。比较次数： " << count << endl; return -1; } int main() { // 测试数据 int list1[] = {3, 6, 2, 10, 1, 8, 5, 7, 4, 9}; int list2[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; int list3[] = {6, 14, 20, 25, 39, 59, 67, 78, 89, 96, 123}; int key1 = 5, key2 = 9, key3 = 9, key4 = 96, key5 = 97; // 顺序查找无序表 cout << "1\n"; sequential_search(list1, sizeof(list1)/sizeof(int), key1); // 顺序查找有序表 cout << "2\n"; sequential_search(list2, sizeof(list2)/sizeof(int), key2); // 折半查找有序表 cout << "3\n"; binary_search(list3, 0, sizeof(list3)/sizeof(int)-1, key3); // 顺序查找无序表 cout << "4\n"; sequential_search(list3, sizeof(list3)/sizeof(int), key4); sequential_search(list3, sizeof(list3)/sizeof(int), key5); // 折半查找有序表 cout << "5\n"; binary_search(list3, 0, sizeof(list3)/sizeof(int)-1, key4); binary_search(list3, 0, sizeof(list3)/sizeof(int)-1, key5); return 0; }

这是一段 C++ 代码，其中实现了顺序查找和折半查找两种查找算法。顺序查找是在无序表中按顺序逐个查找关键字，时间复杂度为 O(n)；折半查找是在有序表中将表分成两半，每次将待查找的关键字与中间位置的关键字进行比较，从而缩小查找范围，时间复杂度为 O(log n)。代码中还定义了几个测试数据和关键字，可以用于测试两种算法的性能。