二分查找
二分查找的思想其实是为了减少搜索范围，每次缩减一半，这样就可以快速找到对象。
1.二分查找的对象
二分查找的对象是有序的数组。如果一个数组没有按顺序排好则无法应用二分查找。
2.二分查找用例
package com.mingguo.zjut.main;
public class BinarySearch {
public static int rank(int key,int a[]){
int L = 0;
int R = a.length - 1;
while(L<=R){
int mid = L +(R-L)/2;
if(a[mid]==key){
return mid;
}else if(a[mid] > key){
R = mid - 1;
}else if(a[mid] < key){
L = mid + 1;
}
}
return -1;
}
public static void main(String[] args) {
int newArray [] = {
1,2,3,4,5,6,7,8
};
System.out.println(rank(1,newArray));
}
}
3.二分查找过程
上述二分查找代码是用rank()函数实现的，该函数接受一个整数和一个已经有序的int数组作为参数。如果该键存在于数组中则返回他的索引，否则返回-1。该算法使用了两个变量L和R，并保证如果该键存在于数组中，则它一定在a[L..R]中，然后方法进入下一次的循环，不断的将数组的中间键（索引为mid）和被查找的键比较。如果查找的键等于a[mid],返回mid；否则算法就会将范围缩小为原来的一半，如果被查找的键小于a[mid]就继续在左半边找，如果被查找的键大于a[mid]就继续在右半边找。算法找到该键或者查找范围为空（L>R）时该过程结束。二分查找之所以快是因为它只需检查很少几个条目（相对于数组的大小）就能找到目标元素（或者确认目标元素不存在）。
