C++实现顺序查找与二分查找

"C++顺序查找" 在C++编程中，顺序查找（Sequential Search）是一种基本的搜索算法，用于在序列或数组中寻找特定元素。这段代码示例演示了如何在自定义的数据结构SSTable中实现顺序查找和二分查找。 首先，我们来看一下SSTable的定义： ```cpp typedef struct { int *elem; int length; } SSTable; ``` 这里定义了一个结构体SSTable，它包含两个成员：一个整型指针elem，用于存储数组元素；以及一个整型变量length，表示数组的长度。 接下来是`Search`函数，实现了顺序查找算法： ```cpp int Search(SSTable ST, int key) { ST.elem[0] = key; for (int i = ST.length; i >= 1; --i) { if (ST.elem[i] == key) return i; } return 0; } ``` 在这个函数中，首先将键值key赋给数组的第一个元素，然后从数组的最后一个元素开始遍历（因为索引是从1到length）。如果找到与key相等的元素，返回其索引。如果遍历完所有元素都没有找到，返回0表示未找到。 然后是`BinarySearch`函数，它实现了更高效的二分查找算法： ```cpp int BinarySearch(SSTable ST, int key) { int low = 1; int high = ST.length; while (low <= high) { int mid = (low + high) / 2; if (ST.elem[mid] == key) { return mid; } else if (ST.elem[mid] < key) { high = mid - 1; } else { low = mid + 1; } }; return 0; } ``` 二分查找适用于已排序的数组。它首先设置查找范围的下限low和上限high，然后不断取中间元素mid与key比较，根据比较结果调整查找范围，直到找到目标元素或者查找范围为空。如果找到目标元素，返回其索引；否则返回0。 在主函数`main`中，创建了一个SSTable对象s，并初始化了一个整型数组a。然后将数组a的元素复制到s.elem中，最后调用`Search`和`BinarySearch`函数，分别对3进行查找并输出结果。 这个程序展示了C++中基本的搜索算法实现，顺序查找适用于任何无序序列，而二分查找则在有序序列中表现出更好的效率。理解这些基础算法对于学习更高级的搜索算法和数据结构至关重要。