c++折半查找算法(实验类型:验证型) 1)问题描述:从键盘读入一串整数和一个待查关键
时间: 2024-01-03 17:02:03 浏览: 46
折半查找算法,也称为二分查找算法,是一种高效的查找方法。该算法适用于已排好序的列表,通过将待查关键字与列表中间的关键字比较,确定待查关键字在列表中的位置,从而缩小了查找范围。
算法步骤如下:
1. 从键盘读入一串整数,将其存储在一个有序列表中。
2. 读入待查关键字。
3. 定义列表的起始索引start为0,结束索引end为列表长度减1。
4. 当start小于等于end时,执行以下步骤。
- 将中间索引mid定义为(start + end)除以2。
- 如果列表中间关键字等于待查关键字,那么返回中间索引。
- 如果列表中间关键字大于待查关键字,那么将end更新为mid-1。
- 如果列表中间关键字小于待查关键字,那么将start更新为mid+1。
5. 若循环结束仍未找到待查关键字,则返回-1表示未找到。
通过实验验证折半查找算法:
假设输入的一串整数为:[2, 4, 6, 8, 10, 12, 14, 16, 18, 20],待查关键字为12。
1. 按照算法步骤,设置start=0, end=9。
2. 中间索引为4,对应的关键字为10,小于12,将start更新为mid+1,即5。
3. 中间索引为7,对应的关键字为16,大于12,将end更新为mid-1,即6。
4. 中间索引为5,对应的关键字为12,等于12,返回中间索引5,表示找到关键字。
5. 实验验证成功。
折半查找算法的时间复杂度为O(logN),N表示列表的长度,相对于线性查找算法,折半查找算法的效率更高。
相关问题
c语言实现折半查找算法的非递归和递归算法。注:算法实现时可以把元素类型均简化为int型。
好的,关于折半查找算法的非递归和递归算法,我可以回答你。首先,折半查找算法(Binary Search)也被称为二分查找算法,在有序数组中查找目标元素的过程中,将数组折半,取中间位置作为比较对象,如果中间元素等于要查找的元素,则查找成功;如果中间元素比要查找的元素大,则在左半部分继续查找;反之,在右半部分查找,直到找到目标元素或查找失败。折半查找算法的时间复杂度为O(log n)。
非递归实现:
int binary_search(int arr[], int left, int right, int target){
while(left <= right){
// 取中间位置
int mid = (left + right) / 2;
// 如果中间元素等于要查找的元素,则查找成功
if(arr[mid] == target){
return mid;
}
// 如果中间元素比要查找的元素大,则在左半部分继续查找
else if(arr[mid] > target){
right = mid - 1;
}
// 在右半部分查找
else{
left = mid + 1;
}
}
// 查找失败
return -1;
}
递归实现:
int binary_search(int arr[], int left, int right, int target){
if(left > right){
// 查找失败
return -1;
}
else{
// 取中间位置
int mid = (left + right) / 2;
// 如果中间元素等于要查找的元素,则查找成功
if(arr[mid] == target){
return mid;
}
else if(arr[mid] > target){
// 在左半部分查找
return binary_search(arr, left, mid - 1, target);
}
else{
// 在右半部分查找
return binary_search(arr, mid + 1, right, target);
}
}
}
以上是折半查找算法的非递归和递归实现,希望回答能够帮到你。
用c++表示解决数据结构问题:建立一个20个以上数据的有序顺序表表中可以仅存放记录的关键字,实现对该有序表的折半查找算法
好的,以下是用 C++ 实现折半查找算法的代码:
```cpp
#include <iostream>
using namespace std;
const int MAX_SIZE = 100;
int a[MAX_SIZE] = {3, 6, 8, 11, 18, 21, 24, 27, 29, 33, 36, 39, 42, 45, 48, 51, 54, 57, 60, 63, 66};
int binarySearch(int key, int low, int high) {
while (low <= high) {
int mid = (low + high) / 2;
if (a[mid] == key) {
return mid;
} else if (a[mid] > key) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return -1;
}
int main() {
int key;
cout << "请输入要查找的数字: ";
cin >> key;
int index = binarySearch(key, 0, 20);
if (index == -1) {
cout << "未找到该数字!" << endl;
} else {
cout << "数字 " << key << " 在第 " << index + 1 << " 个位置" << endl;
}
return 0;
}
```
上述代码中,使用数组 `a` 存储有序表的数据,其中 `binarySearch` 函数为折半查找算法的实现,`key` 为要查找的数字,`low` 和 `high` 分别为有序表的起始位置和终止位置。最后根据查找结果输出相应的信息。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)