设计一个函数模版find,用于对一个有序数组采用二分法查找指定数据的元素下标
时间: 2024-02-03 13:15:09 浏览: 88
图解数据结构二分法查找法
以下是一个使用 C++ 编写的 find 函数模版,用于对有序数组进行二分查找:
```cpp
template <typename T>
int find(const T* arr, int size, const T& target) {
int left = 0;
int right = size - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
}
else if (arr[mid] < target) {
left = mid + 1;
}
else {
right = mid - 1;
}
}
return -1; // 没找到目标元素
}
```
在该函数模版中,参数 `arr` 是指向有序数组的指针,`size` 是数组的大小,`target` 是要查找的目标元素。
函数模版内部使用了二分查找算法,首先将左右边界初始化为数组的首尾元素下标,然后在循环中不断将中间位置的元素与目标元素进行比较,缩小查找范围,直到找到目标元素或者查找范围缩小到空集。如果找到目标元素,则返回其下标;否则返回 -1 表示没找到。
使用该函数模版可以方便地对各种类型的有序数组进行查找,例如:
```cpp
int arr[] = {1, 3, 5, 7, 9};
int idx = find(arr, 5, 5); // 返回 2
```
```cpp
double arr[] = {1.1, 2.2, 3.3, 4.4};
int idx = find(arr, 4, 5.5); // 返回 -1
```
```cpp
std::string arr[] = {"apple", "banana", "orange"};
int idx = find(arr, 3, std::string("banana")); // 返回 1
```
阅读全文