对于有序数组，才能使用二分查找法，需要先排序，常应用于需要多次查找的情况

选定一个标定点，将数组分为左右两个区间，时间复杂度为O(logn)

递归写法

public class Algorithm {

    public static void main(String[] args) {

        Integer[] arr = {1,2,3,4,5,6,7};
        System.out.println(new BinarySearch().search(arr, 4));

    }
}

class BinarySearch {

    public static<E extends Comparable<E>> int search(E[] arr, E target){

        int res = search(arr, 0, arr.length - 1, target);

        return res;
    }

    /**
     * 循环不变量：在arr[left, right]中寻找target
     */
    public static<E extends Comparable<E>> int search(E[] arr, int left, int right, E target){

        if (left > right){
            return -1;
        }

        int mid = left + (right - left) / 2;

        if (arr[mid].compareTo(target) == 0){
            return mid;
        }
        else if (arr[mid].compareTo(target) < 0){
            return search(arr, mid + 1, right, target);
        }
        else {
            return search(arr, left, mid - 1, target);
        }
    }
}

非递归写法

public class Algorithm {

    public static void main(String[] args) {

        Integer[] arr = {1,2,3,4,5,6,7};
        System.out.println(new BinarySearch().search(arr, 4));

    }
}

class BinarySearch {

    public static<E extends Comparable<E>> int search(E[] arr, E target){

        int left = 0;
        int right = arr.length - 1;

        /**
         * 非递归写法，修改边界的范围来循环查找
         */
        while (left <= right) {

            int mid = left + (right - left) / 2;

            if (arr[mid].compareTo(target) == 0) {
                return mid;
            }

            if (arr[mid].compareTo(target) < 0) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return -1;
    }
}