用c++同时实现顺序查找和折半查找的输入和输出
时间: 2024-05-08 10:21:07 浏览: 91
C语言程序设编写程序在数组中查找一个数要求 ⑴用顺序查找实现 ⑵用折半查找实现。 注:若有该数,则输出该数,否则输出“无此数”。
5星 · 资源好评率100%
以下是用 C++ 实现顺序查找和折半查找的代码示例:
顺序查找:
```cpp
#include <iostream>
using namespace std;
int sequentialSearch(int arr[], int n, int key) {
for (int i = 0; i < n; i++) {
if (arr[i] == key) {
return i; // 返回找到的元素下标
}
}
return -1; // 如果未找到,则返回 -1
}
int main() {
int arr[] = { 10, 20, 30, 40, 50 };
int n = sizeof(arr) / sizeof(arr[0]);
int key = 30;
int index = sequentialSearch(arr, n, key);
if (index == -1) {
cout << key << " not found in the array" << endl;
} else {
cout << key << " found at index " << index << endl;
}
return 0;
}
```
折半查找:
```cpp
#include <iostream>
using namespace std;
int binarySearch(int arr[], int n, int key) {
int low = 0, high = n - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (key == arr[mid]) {
return mid; // 返回找到的元素下标
} else if (key < arr[mid]) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return -1; // 如果未找到,则返回 -1
}
int main() {
int arr[] = { 10, 20, 30, 40, 50 };
int n = sizeof(arr) / sizeof(arr[0]);
int key = 30;
int index = binarySearch(arr, n, key);
if (index == -1) {
cout << key << " not found in the array" << endl;
} else {
cout << key << " found at index " << index << endl;
}
return 0;
}
```
以上两段代码分别实现了顺序查找和折半查找,可以根据需要进行输入和输出。其中,顺序查找的时间复杂度为 O(n),折半查找的时间复杂度为 O(log n)。
阅读全文