漫谈递归：二分查找算法的递归实现

还有一个典型的递归例子是对已排序数组的二分查找算法。

现在有一个已经排序好的数组，要在这个数组中查找一个元素，以确定它是否在这个数组中，很一般的想法是顺序检查每个元素，看它是否与待查找元素相同。这个方法很容易想到，但它的效率不能让人满意，它的复杂度是O(n)的。现在我们来看看递归在这里能不能更有效。

还是考虑上面的两个条件：

• 第一：这个问题是否可以分解为形式相同但规模更小的问题？
• 第二：如果存在这样一种分解，那么这种分解是否存在一种简单情境？

考虑条件一：我们可以这样想，如果想把问题的规模缩小，我们应该做什么？

可以的做法是：我们先确定数组中的某些元素与待查元素不同，然后再在剩下的元素中查找，这样就缩小了问题的规模。那么如何确定数组中的某些元素与待查元素不同呢？ 考虑到我们的数组是已经排序的，我们可以通过比较数组的中值元素和待查元素来确定待查元素是在数组的前半段还是后半段。这样我们就得到了一种把问题规模缩小的方法。

接着考虑条件二：简单情境是什么呢？

容易发现，如果中值元素和待查元素相等，就可以确定待查元素是否在数组中了，这是一种简单情境，那么它是不是唯一的简单情境呢？ 考虑元素始终不与中值元素相等，那么我们最终可能得到了一个无法再分的小规模的数组，它只有一个元素，那么我们就可以通过比较这个元素和待查元素来确定最后的结果。这也是一种简单情境。

好了，基于以上的分析，我们发现这个问题可以用递归来解决，二分法的代码如下：

01	#include "stdio.h"

02	#include "stdlib.h"

03

04	void selectionSort(int data[], int count);

05	int binary_search(int *a, int n, int key);

06

07	void main()

08

{

09	int i, key, rs;

10	int arr[10];

11	int count;

12

13	printf("排序前数组为：");

14	srand((int)time(0));

15	for(i=0; i < 10; i++)

16

{

17	arr[i] = rand()%100;

18	printf("%d ",arr[i]);

19

}

20

21	count = sizeof(arr)/sizeof(arr[0]);

22	selectionSort(arr, count);

23

24	printf("\n排序后数组为：");

25	for(i=0; i < 10; i++)

26

{

27	printf("%d ", arr[i]);

28

}

29

30	printf("\n请输入要查找的数字：");

31	scanf("%d",&key);

32

33	rs = binary_search(arr, 10, key);

34	printf("%d ", rs);

35

}

36

37	void selectionSort(int data[], int count)

38

{

39	int i, j, min, temp;

40	for(i = 0; i < count; i ++) {

41	/*find the minimum*/

42

min = i;

43	for(j = i + 1; j < count; j ++)

44	if(data[j] < data[min])

45

min = j;

46	temp = data[i];

47	data[i] = data[min];

48	data[min] = temp;

49

}

50

}

51

52	int binary_search(int *data, int n, int key)

53

{

54

int mid;

55	if(n == 1){

56	return (data[0] == key);

57

}else{

58	mid = n/2;

59	printf("mid=%d\n", data[mid]);

60	if(data[mid-1] == key)

61

return 1;

62	else if(data[mid-1] > key)

63

{

64	printf("key %d 比 data[mid-1] %d 小，取前半段 \n", key, data[mid-1]);

65	return binary_search(&data[0], mid, key);

66

}

67

else

68

{

69	printf("key %d 比 data[mid-1] %d 大，取后半段 \n", key, data[mid-1]);

70	return binary_search(&data[mid], n - mid, key);

71

}

72

}

73

}

程序运行结果：

1	排序前数组为：53 27 26 99 20 17 15 25 23 63

2	排序后数组为：15 17 20 23 25 26 27 53 63 99

3	请输入要查找的数字：20

4

mid=26

5	key 20 比 data[mid-1] 25 小，取前半段

6

mid=20

7	key 20 比 data[mid-1] 17 大，取后半段

8

mid=23

9

1

这个算法的复杂度是O(logn)的，显然要优于先前提到的朴素的顺序查找法。