二分查找

二分查找的思想其实是为了减少搜索范围，每次缩减一半，这样就可以快速找到对象。

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）时该过程结束。二分查找之所以快是因为它只需检查很少几个条目（相对于数组的大小）就能找到目标元素（或者确认目标元素不存在）。