二分查找
数据是海量的，从中提取有价值的信息是必要的，提取的过程也就是查找的过程。 简单粗暴就是顺序查找，任何东西我一个一个来，不管你是有序无序，对我来说 都一样。跟今天咱们所说的二分查找相比，顺序查找是低效的，二分查找可以更 快的查找出结果。但同时，二分查找也是有开销的，如果说我们在一个数组中查找 一个元素，那么二分查找要求这个数组是有序的。构建这个有序的数组就是相对于 顺序查找多出来的开销。
假设我们有这么一个有序数组{0,1,2,3,4,5,6,7,8,9,10,16,35,67,77,778}， 如果想要查找16所在位置，二分查找的思想就是先将这个数组一分为二，找到中间 元素，进行比较，如果大于中间元素，就去右子数组中继续这个过程，如果小于这个 元素就去左子数组中继续这个过程，如果相等，那么就返回这个位置。这个数组有 16个元素，下标是0到15，中间元素下标就是7，下标是7的元素也就是7，16大于7， 于是我们再去下标8到15（右子数组）中重复查找过程，找到新的中间元素是坐标 11，对与元素正好是16，于是返回11。
这个过程可以简单的用递归来实现，代码如下
public static int search(int[] array,int key,int lo,int hi){
if (lo>hi)return -1;
int mid = lo + (hi-lo)/2;
if (key<array[mid])return search(array,key,lo,mid-1);
else if(key>array[mid])return search(array,key,mid+1,hi);
else return mid;
}
也可以采取非递归的方式
public static int search(int[] array,int key,boolean notrecursion){
int lo =0;
int hi = array.length-1;
while (lo<=hi){
int mid = lo +(hi-lo)/2;
if (key<array[mid]) hi=mid-1;
else if (key>array[mid])lo=mid+1;
else return mid;
}
return -1;
}
这个代码实现的就是二分查找，其实我们对这个代码改动一点点就可以实现查找小于 当前元素的元素个数这一功能。以上代码采取返回-1的方式告知用户未查找到此元素， 我们把-1改为lo,这样就实现了查找小于当前元素的元素个数的功能。为什么呢？
对与递归这个示例代码来说，什么时候会进入if(lo>hi)这个分支？只有上层循环lo等 于了hi等于了mid,并且key不等与array[mid]，于是亦或mid-1赋值给了hi,亦或mid +1赋值给了lo,反正使得lo大于了hi，此刻返回lo,lo大于hi,说明array[lo]定是大于 我们所查找的Key,并且lo等于mid+1,于是lo也就是小于于key的元素的数量值。lo正好 等于小于所查找元素的个数。
代码中还有一个需要注意的地方，计算中间元素坐标用的是lo+(hi-lo)/2而不是 (hi+lo)/2这是为什么呢？得出的结果是一样的，只不过前者避免了溢出的发生， 我们使用的Int数据类型，他表示的数是有范围的，如果超出了这个范围发生了 溢出，我们计算出的mid就可能不处在lo和hi之间，二分查找就会失效。
与顺序查找相比，二分查找确实是可以更快的查找出结果，但也正如前文所说， 在构建这个有序数组上存在着一定的开销，也就是我们的插入动作有些缓慢， 为了在保持高效二分查找的同时，也保证插入的高效性，也就需要一个新的数 据结构，这个我们下文再谈。