折半查找法c++
时间: 2023-06-29 09:06:46 浏览: 87
折半查找法也称二分查找法,是一种常用的查找算法,适用于有序序列。以下是 C++ 实现代码示例:
```c++
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);
}
// 如果找不到要查找的元素,则返回 -1
return -1;
}
```
该函数接收一个有序数组 `arr`,要查找的元素 `x`,以及数组的左端点下标 `l` 和右端点下标 `r`。函数通过递归的方式进行查找,如果找到了要查找的元素,则返回它的下标,否则返回 -1。
相关问题
写一段折半查找法完整代码
好的,以下是折半查找法的完整代码:
```c++
#include <iostream>
using namespace std;
int binarySearch(int arr[], int left, int right, int target) {
// 如果左侧索引大于右侧索引,说明查找失败
if (left > right) {
return -1;
}
// 计算中间索引
int mid = left + (right - left) / 2;
// 如果中间元素等于目标值,直接返回中间索引
if (arr[mid] == target) {
return mid;
}
// 如果中间元素大于目标值,继续在左侧查找
else if (arr[mid] > target) {
return binarySearch(arr, left, mid - 1, target);
}
// 如果中间元素小于目标值,继续在右侧查找
else {
return binarySearch(arr, mid + 1, right, target);
}
}
int main() {
int arr[] = {1, 3, 5, 7, 9};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 5;
int result = binarySearch(arr, 0, n - 1, target);
if (result == -1) {
cout << "查找失败" << endl;
}
else {
cout << "查找成功,目标元素的索引为:" << result << endl;
}
return 0;
}
```
这段代码实现了折半查找法,通过递归的方式在有序数组中查找目标元素的索引。在主函数中,我们定义了一个有序数组并指定目标元素为5进行查找,最后输出查找结果。
用顺序查找法、折半查找法对查找表进行查找代码、
好的,我可以为你提供用顺序查找法、折半查找法进行查找的代码。
首先是顺序查找法,它的基本思想是逐个比较查找表中的元素,直到找到目标元素或查找完整个表。以下是一个简单的用 C++ 实现的顺序查找函数:
```cpp
int sequentialSearch(int arr[], int n, int target) {
for (int i = 0; i < n; i++) {
if (arr[i] == target) {
return i; // 找到目标元素,返回其下标
}
}
return -1; // 没有找到目标元素,返回 -1
}
```
其中,`arr` 为查找表,`n` 为表中元素的个数,`target` 为要查找的目标元素。
接下来是折半查找法,它的基本思想是利用有序表的有序性,每次将查找区间缩小一半,直到找到目标元素或查找区间为空。以下是一个简单的用 C++ 实现的折半查找函数:
```cpp
int binarySearch(int arr[], int n, int target) {
int left = 0, right = n - 1; // 查找区间为 [left, right]
while (left <= right) {
int mid = (left + right) / 2; // 计算中间位置
if (arr[mid] == target) {
return mid; // 找到目标元素,返回其下标
} else if (arr[mid] < target) {
left = mid + 1; // 目标元素在右半区间,更新左端点
} else {
right = mid - 1; // 目标元素在左半区间,更新右端点
}
}
return -1; // 没有找到目标元素,返回 -1
}
```
其中,`arr` 为有序表,`n` 为表中元素的个数,`target` 为要查找的目标元素。
希望这些代码能够对你有所帮助!如果你还有其他问题,可以继续向我提出。