设计一个函数模板find,用于对一个有序数组采用二分法查找指定数据的元素下标
时间: 2024-03-02 20:54:24 浏览: 21
好的,以下是实现代码:
```c++
template <typename T>
int find(T arr[], int size, T target) {
int left = 0, right = size - 1, mid;
while (left <= right) {
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; // 没有找到目标元素,返回-1
}
```
这个函数模板接受一个泛型数组 `arr`,数组长度 `size` 和要查找的目标值 `target`,返回目标值在数组中的下标,如果没有找到则返回-1。函数使用经典的二分法查找算法实现。
相关问题
设计一个函数模版find,用于对一个有序数组采用二分法查找指定数据的元素下标
以下是一个使用模板函数实现二分查找的示例代码:
```cpp
template <typename T>
int find(T arr[], int n, T target) {
int l = 0, r = n - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
l = mid + 1;
} else {
r = mid - 1;
}
}
return -1; // 未找到
}
```
该函数模板接受三个参数:
- `arr`:指向有序数组的指针;
- `n`:数组的元素个数;
- `target`:要查找的目标元素。
函数实现中使用了经典的二分查找算法,其中 `l` 和 `r` 分别表示当前查找的区间的左右边界,`mid` 表示区间的中间位置。如果中间元素正好等于目标元素,那么查找成功,返回中间元素的下标;如果中间元素小于目标元素,那么目标元素在右半部分,更新左边界 `l`;否则目标元素在左半部分,更新右边界 `r`。如果最终未找到目标元素,函数返回 `-1`。
设计一个函数模板find,用于对一个有序数组采用二分法查找指定数据的元素下标。用int,char型数据进行测试
以下是一个用于对有序数组采用二分法查找指定数据的元素下标的函数模板find的实现:
```c++
template <typename T>
int find(const T* arr, int length, const T& key) {
int left = 0;
int right = length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] == key) {
return mid;
} else if (arr[mid] < key) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1; // 没有找到
}
```
该函数模板接受一个泛型类型T作为参数,表示要查找的元素类型。函数的第一个参数是一个指向有序数组的指针,第二个参数是数组的长度,第三个参数是要查找的关键字。
函数内部使用了二分法查找指定数据的元素下标,如果找到了则返回下标,否则返回-1表示没有找到。
以下是使用int和char类型数据测试该函数模板的示例代码:
```c++
#include <iostream>
template <typename T>
int find(const T* arr, int length, const T& key) {
int left = 0;
int right = length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] == key) {
return mid;
} else if (arr[mid] < key) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1; // 没有找到
}
int main() {
int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int length = sizeof(arr) / sizeof(int);
int index = find(arr, length, 5);
std::cout << "index of 5: " << index << std::endl;
index = find(arr, length, 10);
std::cout << "index of 10: " << index << std::endl;
char chars[] = {'a', 'b', 'c', 'd', 'e'};
length = sizeof(chars) / sizeof(char);
index = find(chars, length, 'c');
std::cout << "index of 'c': " << index << std::endl;
index = find(chars, length, 'f');
std::cout << "index of 'f': " << index << std::endl;
return 0;
}
```
输出结果:
```
index of 5: 4
index of 10: -1
index of 'c': 2
index of 'f': -1
```