用C++代码实现基于有序顺序表的折半搜索,写出主函数
时间: 2024-02-09 07:08:06 浏览: 28
好的,以下是C++代码实现基于有序顺序表的折半搜索的示例:
```cpp
#include <iostream>
using namespace std;
const int MAXSIZE = 20; // 定义顺序表的最大长度
// 定义顺序表结构体
struct SeqList {
int data[MAXSIZE];
int length;
};
// 折半搜索函数
int binarySearch(SeqList list, int key) {
int low = 0; // 搜索区间的左端点
int high = list.length - 1; // 搜索区间的右端点
int mid; // 搜索区间的中间位置
while (low <= high) {
mid = (low + high) / 2;
if (list.data[mid] == key) { // 找到了目标元素
return mid;
} else if (list.data[mid] > key) { // 目标元素在左半区间
high = mid - 1;
} else { // 目标元素在右半区间
low = mid + 1;
}
}
return -1; // 没有找到目标元素
}
// 主函数
int main() {
SeqList list = { {1, 3, 5, 7, 9, 11, 13, 15, 17, 19}, 10 };
int key;
cout << "请输入要搜索的元素:";
cin >> key;
int index = binarySearch(list, key);
if (index == -1) {
cout << "未找到该元素!" << endl;
} else {
cout << "该元素的下标为:" << index << endl;
}
return 0;
}
```
在上面的代码中,我们首先定义了一个顺序表结构体 `SeqList`,其中包含一个整型数组 `data` 和一个整型变量 `length`,表示顺序表的元素和长度。然后,我们定义了一个折半搜索函数 `binarySearch`,用于在有序顺序表中查找目标元素 `key`,并返回其下标。最后,在主函数中,我们创建了一个有序顺序表,从用户输入获取要搜索的元素,并调用 `binarySearch` 函数进行搜索,输出搜索结果。
希望能够帮到你,有什么问题可以继续问我哦!