递归函数之二分法查找
试题描述
编写形如int fun(int array[], int key, int low, int high)的递归函数,该函数的返回值是整数,通过递归调用的方法在数组中查找指定key值的元素,并返回找到的数组元素位置;若找不到,则函数返回-1。
在主函数main()中输入数组元素个数N、N个从小到大排好序的整数、要查找的值key,并将N个整数存入数组arr中;然后调用函数fun(int[], int, int, int),并将arr、key、0和N - 1作为该函数的实参;最后输出该函数的返回值到屏幕。
输入
输入包含三行:
第一行是N(0 < N < 1000)。
第二行是N个整数,代表从小到大排好序的数组各个元素值(没有重复的元素值),邻近两数之间用一个空格隔开。
第三行是要查找的元素key。
输出
输出元素key在数组中的下标位置。
输入示例1
10
10 20 30 40 50 60 70 80 90 100
40
输出示例1
3
输入示例2
10
10 20 30 40 50 60 70 80 90 100
46
输出示例2
-1
数据范围
输入和输出均为int范围的整数
函数如下:(注意终止条件要设好)
#include<stdio.h>
int search(int arr[], int key, int low, int high)
{
int mid =(low + high)/2;
if(low>high)
return -1;
if(key==arr[mid])
return mid;
else if(key<arr[mid])
return search(arr,key,low,mid-1);
else return search(arr,key,mid+1,high);
}
int main()
{
int arr[1000],key,N,x;
int i;
scanf("%d",&N);
for(i=0;i<N;i++)
scanf("%d",&arr[i]);
scanf("%d",&key);
x=search(arr,key,0,N-1);
printf("%d",x);
return 0;
}
版权声明:本文为m0_73922547原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接和本声明。