#include <iostream>
int find(int arr[], int low, int high, int n) //使用折半查找法的函数要求被查找数组已被排序
{
int mid = (high + low) / 2; // 找出数组中间元素的下标
if (arr[mid] == n) // 如果找到数据,返回数据在数组中的位置,结束递归调用
return mid;
else if (mid == high || mid == low) // 如果数组中不存在该数据,返回-1
return -1;
else if (arr[mid] < n) // 如果中间元素小于被查找元素,则到数组后半段进行查找
return find(arr, mid + 1, high, n);
else // 如果中间元素大于被查找元素,则到数组前半段进行查找
return find(arr, low, mid, n);
} // find函数也可以使用迭代实现
int main()
{
int arr[11] = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89};
int pos = find(arr, 0, 10, 55);
std::cout << "55 = arr[" << pos << "]\n";
pos = find(arr, 0, 10, 1);
std::cout << "1 = arr[" << pos << "]\n"; //这里的pos = 1,说明如果数组中有重复元素折半查找法将查找下标值较大的元素
return 0;
}
这是我的 |