问题4：如何使用递归与非递归实现二分查找？

    二分查找法也称为折半查找法，它的思想是每次都与序列的中间元素进行比较。

二分查找的一个前提条件是数组是有序的。假设数组array为递增序列，findData为

要找的数，n为数组长度，首先将n个元素分成个数大致相同的两半，取array[n/2]与

要查找的值findData进行比较，如果findData等于array[n/2]，则找到findData,算法结束；

如果findData<array[n/2],则只要在数组array的左半部分继续查找findData;如果findData>array[n/2],

则只要在数组array的左半部分继续查找即可。

#include <stdio.h>

//非递归算法，如果存在返回其在数组中的位置，不存在则返回-1
int binarySearch(int a[], int len, int findData)
{
  if(a == NULL || len <= 0)
     return -1;
  int start = 0;
  int end = len-1;
  while(start <= end)
  {
     int mid = start + (end-start)/2;
 if(findData == a[mid])
    return mid;
     else if(findData > a[mid])
    start = mid+1;
 else
    end = mid-1;
  }
  return -1;
}

//递归算法
int binarySearchRecursion(int a[], int findData, int start, int end)
{
   if(start > end)
     return -1;
   int mid = start + (end-start)/2;
   if(findData == a[mid])
     return mid;
   else if(findData > a[mid])
     return binarySearchRecursion(a, findData, mid+1, end);
   else
     return binarySearchRecursion(a, findData, start, mid-1);
}

int binarySearchRecursion1(int a[], int len, int findData)
{
   if(a == NULL || len <= 0)
     return -1;
   return binarySearchRecursion(a, findData, 0, len-1);
}

int main(void)
{
  int a[] = {1, 3, 4, 5, 6, 7, 8, 9};
  int length = sizeof(a)/sizeof(a[0]);
  int index = binarySearch(a, length, 4);
  int index2 = binarySearchRecursion1(a, length, 10);
  printf("%d\n%d\n", index, index2);
  return 0;
}

程序运行结果为：

2

-1