/**
* 二分法 :用折半查找法在一组排好序(递增有序或递减有序)的值中查找某个数据。
*
* 基本思想：
*
* 首先将待查数据k与排好序（递增有序）的一组数据的中间位置上的数据进行比较， 若相等，则查找成功；
* 若k>a[mid]，则待查数据k只可能出现在右半部a[mid+1…n]中,则应在这个右半部中再进行折半查找；
* 若k<a[mid]，则待查数据k只可能出现在左半部a[1…mid-1]中,则应在这个左半部中再进行折半查找；
* 这样通过逐步缩小查找范围，直到找到或找不到该数据k为止。
*
* @author Administrator
*
*/
public class BinarySearch
{
public static int binarySearch(int[] a, int key)
{
if (a == null || a.length == 0)
{
return -1;
}
// 开始位置
int first = 0;
// 结束位置
int last = a.length - 1;
// 中间位置
int mid;
// 如果开始时,小于则结束.
while (first < last)
{
mid = (first + last) / 2;
// 如果等于key,返回这个数在数组中的位置.
if (a[mid] == key)
return mid;
// 如果大于key,则在左边.
if (a[mid] > key)
last = mid - 1;
// 如果小于key,则在右边
if (a[mid] < key)
first = mid + 1;
}
return -1;
}
public static void main(String[] args)
{
int[] a =
{ 1, 3, 4, 5, 8, 7, 9, 11, 15 };
System.out.println(binarySearch(a, 9));
}
}