用c或者c++语言设计顺序查找算法和折半查找算法。
时间: 2024-02-25 14:55:35 浏览: 76
好的,我会分别介绍一下顺序查找算法和折半查找算法的C++实现。
1. 顺序查找算法(Sequential Search)
顺序查找法又称线性查找,是一种最简单、最基本的查找方法。它的基本思路是将待查找的元素依次与数据结构中的每个元素进行比较,直到找到目标元素或者搜索完所有元素为止。
下面是C++实现代码:
```c++
#include <iostream>
using namespace std;
int sequentialSearch(int arr[], int n, int x) {
for (int i = 0; i < n; i++) {
if (arr[i] == x) {
return i;
}
}
return -1;
}
int main() {
int arr[] = {1, 3, 5, 7, 9};
int n = sizeof(arr) / sizeof(arr[0]);
int x = 7;
int result = sequentialSearch(arr, n, x);
if (result == -1) {
cout << "Element is not present in array" << endl;
} else {
cout << "Element is present at index " << result << endl;
}
return 0;
}
```
2. 折半查找算法(Binary Search)
折半查找算法又称二分查找,是一种效率较高的查找方法。它的基本思路是:先确定待查找区间的中间位置,然后将待查找元素与中间位置的元素进行比较。如果相等,则返回查找结果;如果不相等,则根据待查找元素与中间位置元素的大小关系,确定待查找区间的左半部分或右半部分,再对该部分进行折半查找,直到找到目标元素或者待查找区间为空为止。
下面是C++实现代码:
```c++
#include <iostream>
using namespace std;
int binarySearch(int arr[], int l, int r, int x) {
if (r >= l) {
int mid = l + (r - l) / 2;
if (arr[mid] == x) {
return mid;
}
if (arr[mid] > x) {
return binarySearch(arr, l, mid - 1, x);
}
return binarySearch(arr, mid + 1, r, x);
}
return -1;
}
int main() {
int arr[] = {1, 3, 5, 7, 9};
int n = sizeof(arr) / sizeof(arr[0]);
int x = 7;
int result = binarySearch(arr, 0, n - 1, x);
if (result == -1) {
cout << "Element is not present in array" << endl;
} else {
cout << "Element is present at index " << result << endl;
}
return 0;
}
```
阅读全文