用c++实现折返查找和顺序查找
时间: 2023-08-24 12:14:28 浏览: 43
好的,下面是C++实现折返查找和顺序查找的示例代码:
```c++
#include <iostream>
#include <vector>
using namespace std;
// 折返查找
int foldSearch(const vector<int>& arr, int target) {
int left = 0, right = arr.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
}
if (arr[left] <= arr[mid]) {
if (arr[left] <= target && target < arr[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else {
if (arr[mid] < target && target <= arr[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return -1;
}
// 顺序查找
int seqSearch(const vector<int>& arr, int target) {
for (int i = 0; i < arr.size(); i++) {
if (arr[i] == target) {
return i;
}
}
return -1;
}
int main() {
vector<int> arr = {4, 5, 6, 7, 0, 1, 2};
int target = 1;
int index1 = foldSearch(arr, target);
int index2 = seqSearch(arr, target);
cout << "折返查找结果:" << index1 << endl;
cout << "顺序查找结果:" << index2 << endl;
return 0;
}
```
运行结果:
```
折返查找结果:5
顺序查找结果:5
```
其中,`foldSearch`函数是折返查找的实现,`seqSearch`函数是顺序查找的实现。在`main`函数中,我们定义了一个含有七个元素的数组`arr`,并且将目标值`target`设置为1。然后,分别调用`foldSearch`和`seqSearch`函数,输出它们的返回值。
注意:折返查找的前提条件是数组本身是有序的,且不含有重复元素。如果数组中有重复元素,可以采用顺序查找等其他方法。