本文简单介绍二分查找的递归算法。
对一个有序的列表通过按中间元素切分搜索空间进行快速查找的，也可以通过递归方法实现。
虽然该算法实际应用中较少，但其中的递归思路大家可以熟悉一下，为学习数据结构中树的相关内容作一个铺垫。前后代码都简单易懂，因而不作过多的赘述，诸位读者直接阅读代码即可。唯一的点在于，递归算法中找不到的情况“return -1”的书写位置和条件需要注意。
本文的呈现想法和下面这篇文章相同，作为开拓思路、加深对递归函数的理解而为之。其实很多基础的算法，包括斐波那契数列、闰年等，都可以用递归实现。递归思路能将复杂的问题呈现以简单的思路，这是它的优势。通过简单问题的递归实现，大家可以提前熟悉递归的构造和运用，为后续学习数据结构“树”的相关内容作铺垫。
递归实现素数判断
原二分查找代码
int binarySearch(int* arr,int left,int right,int key){ while(left <= right){ int mid = (left+right)/2; if(key > arr[mid]){ left = mid + 1; }else if(key < arr[mid]){ right = mid - 1; }else{ return mid; } } return -1; }
递归二分查找代码
思路：将迭代换为递归
1. 找重复（规模更小）
每次重复的过程均为：判断目标数字key与中间元素arr[mid]的大小 --> 缩小范围
2. 找变化（确定参数）
变化的量始终是查找范围的边界（left和right），将它们写入递归函数的参数列表。
3. 找出口
当找到目标数字时，递归函数开始返回值mid，因而条件即为 key == arr[mid]
int binarySearch(int* arr,int left,int right,int key){ if(left > right){ return -1; } int mid = (left+right)/2; if(key > arr[mid]){ //left = mid + 1; binarySearch(arr,mid + 1,right,key); }else if(key < arr[mid]){ //right = mid - 1; binarySearch(arr,left,mid-1,key); }else if(key == arr[mid]){ return mid; } }
时间复杂度与空间复杂度均为O(logN)
