二分查找法

package keyword;

/**
 * @author zhou.fa@diligentfirst.com
 * @projectName lucene-5.0.0
 * @createDate 2016-12-19
 */

/**
 * 二分查找法主要是解决在“一堆数中找出指定的数”的这类问题
 *
 * 然而这个堆数需要满足以下两个条件：
 * 1.必须是有序的
 * 2.必须是数组
 * 所以二分查找法是作用在有序数组上的功能
 */
public class BinarySearch {

    public static void main(String[] args) {
        int[] a = new int[2<<6+1];
        for (int i = 0; i< 2<<6; i++){
            a[i] = i;
        }
        int po = new BinarySearch().getPos(a, a.length, 20);
        int po2 = new BinarySearch().secFun(a, a.length, 70);
        System.out.println("方法1："+po);
        System.out.println("方法2："+po2);

    }

    private int getPos(int[] a, int length, int val) {
        return recursionFun(a, val, 0, length-1);
    }

//递归
    private int recursionFun(int[] a, int val, int start, int end) {
        if (start > end) {
            return -1;
        }

        if (a[start] == val) {
            return start;
        }

        int middle = (start + end) / 2;
        if (val > a[middle]) {
            start = middle + 1;
            return recursionFun(a, val, start, end);
        }

        if (val < a[middle]) {
            end = middle - 1;
            return recursionFun(a, val, start, end);
        }

        if (val == a[middle]) {
            return middle;
        }
        return -1;
    }

//非递归
    private int secFun(int[] a, int len, int val) {
        int start = 0;
        int high = len - 1;
        while (start <= high) {
            int middle = (high - start) / 2 + start;
            if (a[middle] == val) {
                return middle;
            } else if (a[middle] > val) {
                high = middle - 1;
            } else {
                start = middle + 1;
            }
        }
        return -1;
    }
}