用c++语言设计顺序查找算法和折半查找算法。
时间: 2024-02-25 15:54:59 浏览: 30
顺序查找算法(线性查找):
```c++
int seqSearch(int arr[], int n, int x)
{
for (int i = 0; i < n; i++) {
if (arr[i] == x)
return i;
}
return -1;
}
```
折半查找算法(二分查找):
```c++
int binarySearch(int arr[], int n, int x)
{
int left = 0, right = n - 1, mid;
while (left <= right) {
mid = (left + right) / 2;
if (arr[mid] == x)
return mid;
else if (arr[mid] < x)
left = mid + 1;
else
right = mid - 1;
}
return -1;
}
```
以上是两种常见的查找算法,其中顺序查找算法的时间复杂度为O(n),折半查找算法的时间复杂度为O(log n),因此在查找数据较少的情况下,可以采用顺序查找算法,而在数据量很大的情况下,则需要采用折半查找算法。
相关问题
用c或者c++语言设计顺序查找算法和折半查找算法。
好的,我会分别介绍一下顺序查找算法和折半查找算法的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;
}
```
C++实现查找算法和折半查找算法
1. 查找算法(线性查找)
线性查找又叫顺序查找,是一种基础的查找算法。顾名思义,就是按照数据的顺序依次进行查找,直到找到目标数据或者遍历完整个数据集为止。
C++代码实现如下:
```c++
#include <iostream>
using namespace std;
int search(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[] = { 2, 5, 3, 7, 9, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
int x = 7;
int index = search(arr, n, x);
if (index == -1) {
cout << "未找到目标数据!" << endl;
} else {
cout << "目标数据在数组中的下标为:" << index << endl;
}
return 0;
}
```
2. 折半查找算法
折半查找又叫二分查找,是一种高效的查找算法。前提条件是数据已经排好序。折半查找的思路是将数据集分成两部分,判断目标数据在哪一部分,然后在该部分中继续进行查找,直到找到目标数据或者确定目标数据不存在为止。
C++代码实现如下:
```c++
#include <iostream>
using namespace std;
int binarySearch(int arr[], int low, int high, int x) {
if (low > high) {
return -1; // 未找到目标数据
}
int mid = (low + high) / 2;
if (arr[mid] == x) {
return mid;
} else if (arr[mid] > x) {
return binarySearch(arr, low, mid - 1, x);
} else {
return binarySearch(arr, mid + 1, high, x);
}
}
int main() {
int arr[] = { 1, 2, 3, 5, 7, 9 };
int n = sizeof(arr) / sizeof(arr[0]);
int x = 7;
int index = binarySearch(arr, 0, n - 1, x);
if (index == -1) {
cout << "未找到目标数据!" << endl;
} else {
cout << "目标数据在数组中的下标为:" << index << endl;
}
return 0;
}
```