用c++实现升序序列的折半查找
时间: 2024-10-20 08:04:58 浏览: 13
在C++中,折半查找,也称为二分查找,通常用于已排序数组中快速找到特定元素。以下是使用C++实现升序序列的折半查找算法:
```cpp
#include <iostream>
// 定义折半查找函数
int binarySearch(int arr[], int left, int right, int target) {
if (right >= left) {
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);
}
// 如果未找到,返回 -1 表示目标不存在于数组中
return -1;
}
int main() {
int arr[] = {1, 3, 5, 7, 9, 11, 13};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 7; // 搜索的目标值
int result = binarySearch(arr, 0, n - 1, target);
if (result != -1)
std::cout << "Element found at index: " << result << std::endl;
else
std::cout << "Element not found in the array." << std::endl;
return 0;
}
```
在这个例子中,`binarySearch` 函数接收一个整数数组、两个边界指针(left 和 right)、以及要查找的目标值。它反复将搜索范围减半直到找到目标或搜索范围为空。
阅读全文