二分查找

1. 概念
   二分查找又叫折半查找，从排序数组中查找元素的位置。

2. 图示

   
   二分查找
3. Java实现

public class BinarySearch {
    public static void main(String[] args) {
        int[] array = new int[7];
        for (int i = 0; i < array.length; i++) {
            array[i] = i + 1;
        }
        if (binarySearch(array, 0)) System.out.println("找到");
        else System.out.println("没找到");
    }

    private static boolean binarySearch(int[] array, int target) {
        return array.length != 0 && recursion(array, 0, array.length - 1, target);
//        return array.length != 0 && nonRecursion(array, target);
    }

    private static boolean recursion(int[] array, int low, int high, int target) {
        int mid = (low + high) >> 1;
        System.out.println("low:" + low + ",mid:" + mid + ",high:" + high);
        if (low <= high) {
            if (array[mid] > target) return recursion(array, low, mid - 1, target);
            else if (array[mid] < target) return recursion(array, mid + 1, high, target);
            else return array[mid] == target;
        } else
            return false;
    }

    //非递归
    private static boolean nonRecursion(int[] array, int target) {
        int low = 0;
        int high = array.length - 1;
        int mid;
        while (low <= high) {
            mid = (low + high) >> 1;
            if (array[mid] > target) high = mid - 1;
            else if (array[mid] < target) low = mid + 1;
            else return array[mid] == target;
        }

        return false;
    }
}

4. 复杂度
   T(n)=T(n/2)+θ(1){比较}=θ(1)+....+θ(1){total log2(n)}=θ(log2(n))