java二分查找

什么是二分查找(折半查找法)
在一个有序序列中，每次取中间位置的值与待查关键字比较，如果中间位置的值比待查关键字大，则在前半部分循环这个查找的过程，如果中间位置的值比待查关键字小，则在后半部分循环这个查找的过程。直到查找到了为止，否则序列中没有待查的关键字。

两种实现方式
1.递归二分查找

public class BinarySearch {
    public static void main(String[] args) {
        int[] a = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        int result = search(a, 0, a.length - 1, 10);
        System.out.println(String.format("position:%d", result));
    }

    /**
     * 递归二分查找实现
     * @param a 查找的有序序列
     * @param left 左边界
     * @param right 右边界
     * @param key 查找的值
     * @return
     * */
    private static int search(int[] a, int left, int right, int key) {
        if (left > right) {
            return -1;
        }

        int mid = (left + right) / 2;
        if (a[mid] > key) {
           return search(a, left, mid - 1, key);
        }

        if (a[mid] < key) {
            return search(a, mid + 1, right, key);
        }

        return mid;

    }
}

2.迭代二分查找

public class BinarySearch2 {
    public static void main(String[] args) {
        int[] a = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        int result = search(a, 0, a.length - 1, 5);
        System.out.println(String.format("position:%d", result));
    }

    /**
     * 递归二分查找实现
     * @param a 查找的有序序列
     * @param left 左边界
     * @param right 右边界
     * @param key 查找的值
     * @return
     * */
    private static int search(int[] a, int left, int right, int key) {
        while (left <= right) {
            int mid = (left + right) / 2;

            if (a[mid] == key) {
                return mid;
            } else if (a[mid] > key) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }

        }

        return -1;
    }
}

二分查找比较次数少，查找速度快，平均性能好，但是要求为有序序列