二分查找的递归和循坏实现法
递归总有一个最简单的情况-方法的第一条语句总是包含return的条件语句；
递归调用总是去尝试解决一个规模更小的子问题，这样递归才能收敛到最简单的情况;
递归调用的父问题和尝试解决的子问题之间不应该有交集；
二分查找：
public static int rank(int key, int[] a) {
return rank(key, a, 0, a.length - 1);
}
public static int rank(int key, int[] a, int lo, int hi) {
if(lo > hi)
return -1;
int mid = lo + (hi - lo) / 2; //数组并没有被拆分，所以这里(hi - lo)/2必须再加上lo
if(key < a[mid]) return rank(key, a, lo, mid - 1);
else if(key > a[mid] return rank(key, a, mid +1, hi);
else return mid;
}
//如果原始的方法参数不怎么适合递归或者不够递归方法，就另写一个满足要求的递归方法，用原始的调用之；
比如二分查找的时候，并没有给定递归时需要的低坐标和高坐标，如果坚持要在原始方法中使用递归，那么必须对数组进行拆分和复制，效率低下，浪费空间；
在不拆分数组的情况下，“父问题和子问题之间不应该有交集“， 所以mid不是简单的lo + hi /2了；mid不用再被传给子问题，因为== mid的话就是解了已经，低位传lo到mid-1；高位传mid + 1到hi；
-------------------------------------------
循环实现：
int lo = 0;
int hi = a.length - 1;
while(lo <= hi) {
int mid = lo + (hi - lo) / 2; //不拆分数组的话，始终是这个公式
if(key < a[mi]) hi = mid - 1;
if(key > a[mi]) lo = mid + 1;
else return mid;
}
return -1;
