题目

给出在一个递增有序表A中采用二分查找算法查找值为k的关键字的递归算法。

分析

即二分查找的算法。

代码

核心代码：

/* 二分查找的核心算法 */
/* A[]指的是要查找的数组；low指的是开始下标；high指的是结束下标；k指的是要查找的关键字k */ 
int BSearch(int A[],int low,int high,int k) {
	int mid;// 中间下标
	if(low>high) {
		return -1;
	} else {
		mid=(low+high)/2;
		if(k<A[mid]) {
			return BSearch(A,low,mid-1,k);// 在右端查找
		} else if(k==A[mid]) {
			return mid;// 查找了返回下标
		} else {
			return BSearch(A,mid+1,high,k);// 在左端中查找
		}
	}
}

完整代码：

#include<stdio.h>
#include<stdlib.h>

#define maxSize 10

/* 二分查找的核心算法 */
/* A[]指的是要查找的数组；low指的是开始下标；high指的是结束下标；k指的是要查找的关键字k */ 
int BSearch(int A[],int low,int high,int k) {
	int mid;// 中间下标
	if(low>high) {
		return -1;
	} else {
		mid=(low+high)/2;
		if(k<A[mid]) {
			return BSearch(A,low,mid-1,k);// 在右端查找
		} else if(k==A[mid]) {
			return mid;// 查找了返回下标
		} else {
			return BSearch(A,mid+1,high,k);// 在左端中查找
		}
	}
}

int main() {
	int nums[]= {1,2,3,4,5,6,7,8,9};
	int n=9;
	int k=6;
	printf("k的下标：%d",BSearch(nums,0,n-1,k));

	return 0;
}

运行结果：