写一个三分检索程序,首先检查n/3的元素是否等于某个x的值,然后检查2n/3处的元素,这样,或者找到或者把集合缩小到原来的1/3.找到输出元素下标,否则输出-1.
时间: 2024-03-17 16:42:04 浏览: 54
好的,我可以为您编写一个C++的三分检索程序,代码如下:
```cpp
#include <iostream>
#include <vector>
using namespace std;
int ternary_search(vector<int>& arr, int x) {
int n = arr.size();
int left = 0, right = n - 1;
while (left <= right) {
int mid1 = left + (right - left) / 3;
int mid2 = right - (right - left) / 3;
if (arr[mid1] == x) {
return mid1;
} else if (arr[mid2] == x) {
return mid2;
} else if (x < arr[mid1]) {
right = mid1 - 1;
} else if (x > arr[mid2]) {
left = mid2 + 1;
} else {
left = mid1 + 1;
right = mid2 - 1;
}
}
return -1;
}
int main() {
vector<int> arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int x = 5;
int index = ternary_search(arr, x);
if (index == -1) {
cout << "Not found" << endl;
} else {
cout << "Found at index " << index << endl;
}
return 0;
}
```
这个程序的实现和上一个Python程序的实现类似,都是通过计算中间索引来将数组分成三个部分。不同之处在于,这个程序使用了C++标准库中的vector来存储数组。
在主函数中,我们创建了一个大小为9的有序数组,然后在其中查找值为5的元素。如果找到了,就输出该元素的索引;否则,就输出"Not found"。
希望这个程序对您有帮助!
阅读全文