给出在有序数组a中查找数据元素×是否存在的递归算法。
时间: 2023-04-06 12:01:46 浏览: 89
可以使用二分查找的递归算法来查找数据元素×是否存在于有序数组a中。具体实现方法如下:
1. 定义递归函数binarySearch(a, low, high, x),其中a为有序数组,low和high分别为数组的起始和结束位置,x为要查找的数据元素。
2. 如果low > high,则说明数组中不存在数据元素x,返回-1。
3. 否则,计算数组中间位置mid = (low + high) / 2。
4. 如果a[mid] == x,则说明数据元素x存在于数组中,返回mid。
5. 如果a[mid] > x,则说明数据元素x可能存在于数组的左半部分,递归调用binarySearch(a, low, mid-1, x)。
6. 如果a[mid] < x,则说明数据元素x可能存在于数组的右半部分,递归调用binarySearch(a, mid+1, high, x)。
7. 返回递归调用的结果。
最终的递归算法实现如下:
int binarySearch(int a[], int low, int high, int x) {
if (low > high) {
return -1;
}
int mid = (low + high) / 2;
if (a[mid] == x) {
return mid;
} else if (a[mid] > x) {
return binarySearch(a, low, mid-1, x);
} else {
return binarySearch(a, mid+1, high, x);
}
}