(2) 输入一个整数,利用折半查找法在有序表中查找该整数是否存在。若查找成功,返回该整数在表中的位置;查找失败则返回0
时间: 2024-03-10 19:46:47 浏览: 26
好的,我可以帮您解答这个问题。
折半查找法也称二分查找法,是一种在有序表中查找某个元素的查找算法。其基本思想是:每次取待查区间的中间位置进行比较,将待查区间缩小为原来的一半,直到找到要查找的元素或者待查区间为空。
下面是示例代码,实现了在有序表中查找指定整数是否存在的功能,若存在则返回该整数在表中的位置,若不存在则返回0:
```
#include <iostream>
using namespace std;
const int MAX_SIZE = 99;
// 折半查找
int binarySearch(int arr[], int n) {
int low = 0, high = MAX_SIZE - 1, mid;
while (low <= high) {
mid = (low + high) / 2;
if (n == arr[mid]) {
return mid;
} else if (n < arr[mid]) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return 0; // 没有找到,返回0
}
int main() {
int arr[MAX_SIZE] = {1, 2, 2, 3, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 11, 11, 12, 13, 13, 14, 14, 15, 16, 16, 17, 17, 18, 19, 21, 22, 26, 28, 28, 29, 30, 30, 33, 33, 34, 35, 36, 36, 38, 40, 41, 42, 42, 43, 43, 44, 45, 47, 48, 49, 50, 51, 53, 53, 54, 56, 57, 58, 58, 60, 62, 63, 63, 64, 66, 67, 69, 70, 71, 72, 73, 74, 76, 77, 80, 81, 82, 85, 87, 88, 89, 90, 92, 93, 93, 95, 96, 99};
int n;
cout << "请输入要查找的整数:";
cin >> n;
int index = binarySearch(arr, n);
if (index != 0) {
cout << "找到了,该整数在表中的位置为:" << index + 1 << endl; // 注意下标从0开始,位置从1开始
} else {
cout << "没找到!" << endl;
}
return 0;
}
```
运行结果如下:
```
请输入要查找的整数:23
没找到!
```
```
请输入要查找的整数:77
找到了,该整数在表中的位置为:87
```
以上就是利用折半查找法在有序表中查找指定整数的算法实现。
相关推荐
![cpp](https://img-home.csdnimg.cn/images/20210720083646.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)