/*
算法：当数据量很大适宜采用该方法。采用二分法查找时，数据需是有序不重复的。
基本思想：
假设数据是按升序排序的，对于给定值x，从序列的中间位置开始比较，
如果当前位置值等于 x，则查找成功；
若 x 小于当前位置值，则在数列的前半段中查找；
若 x 大于当前位置值则在数列的后半段中继续查找，直到找到为止。
查找 key=58
数组arr： | 10 | 16 | 38 | 58 | 118|
==========================
第一次: | 10 | 16 | 38 | 58 | 118| //min=0,max=4,mid=2,key>arr[mid],在后半段查找；
^ ^ ^
第二次: | 10 | 16 | 38 | 58 | 118| //min=3,max=4,mid=3,key==arr[mid],则key查找到；
*/
public static int binarySearch(int[] arr, int key)
{
int min = 0; //定义小标，并初始化为0；
int max = arr.length-1; //定义大标，并初始化为数组的最后的坐标；
int mid = (min+max)/2; //定义中标，并初始化值为(min+max)/2,比如int(0+5)/2=2l
while(arr[mid]!=key) //当中标的值与给定的值不一样时，
{
if(key>arr[mid]) //如果给定的值大于中标，
{
min = mid + 1; //则小标=中标+1；比较后半段
}else if (key<arr[mid]) //如果给定的值小于中标
{
max = mid - 1; //则小标=中标-1；比较后半段
}
if(min>max) //如果小标>大标，没有找到给定的值；
{
return -1; //返回-1，代表Error
}
mid = (min+max)/2; //设置中标=（小标+大标）/2;
}
return mid; //arr[mid]==key,则返回中标;
}
public static void main(String[] args)
{
int[] arr = new int[]{10,16,38,58,118};
int index = binarySearch(arr,58);
System.out.println("index="+index);
index = binarySearch(arr,8);
System.out.println("index="+index);
}
#运行结果：
index=3
index=-1
